오일러의 체(Linear Sieve)로 O(logn) 소인수 분해 하기

이 게시글에서는 linear sieve 또는 오일러의 체라 불리는 알고리즘에 대해 알아보고 그 구현을 배우도록 한다.

Linear Sieve

Linear sieve는 에라토스테네스의 체를 개선하여 N 이하의 소수를 $O(N)$ 만에 찾고 N 이하 자연수의 소인수 분해를 $O(\log N)$에 할 수 있게 만들어 준다.

 

과정은 다음과 같다.

 

소수의 여부 대신 해당 수의 최소 소인수(Smallest Prime Factor. 이하 spf)를 나타내는 체(배열)를 둔다.

 

spf 체를 순회하면서 해당 index의 값이 비어있는(0) 경우 소수가 된다. 그래서 spf[index] = index가 되고 index를 소수 집합에 추가한다.

 

그런 다음 현재까지 판별한 모든 소수들에 대해 반복문을 돌면서 spf[index * 소수] = 소수 계산을 수행한다. 그렇게 되면 spf[index * 소수]는 소수가 아니면서 그 소인수는 소수라는 정보를 가지게 된다.

 

이때 index가 현재 순회 중인 소수와 나누어 떨어지면 반복문을 종료한다.

 

이 과정을 N까지 반복하면 $O(N)$으로 N 이하 소수의 개수와 각 수의 spf를 구할 수 있다.

원리

위 과정을 보면서 정말로 $O(N)$이 맞는지, 왜 index마다 현재 가지고 있는 소수들에 대해서만 계산을 할까? 그리고 이렇게 저장한 spf가 정말 spf가 맞는 걸까?

 

체를 통해 생성한 소수 목록은 정렬되어 있는 상태이다. 그러므로 작은 소수부터 곱하게 된다.

 

따라서 index와 소수들을 곱하면서 첫번째로 만난 나누어 떨어지는 소수가 spf인건 당연하므로 그다음 수들에 대해 spf 갱신을 해주면 안 되는 것을 알 수 있다.

 

spf 갱신은 하지 않아도 방문은 해야될수도 있지 않을까? 이는 귀류법으로 증명할 수 있다.

 

나누어 떨어지는 소수를 발견한 이후 반복문을 종료하지 않아도 중복 방문을 하지 않는다고 해보자.

 

이럴 경우 14와 21에 대해 42를 중복 방문하는 경우가 생기고 이는 모순이다.

 

따라서 나누어 떨어지는 소수를 만났을 때 반복을 종료하여 $O(N)$의 시간 복잡도로 소수 집합과 spf를 구할 수 있음이 증명된다.

 

이 증명은 정확하지 않을 수 있으므로 이 글을 참조하는 것을 권장한다.

구현

C++ 함수로 구현하면 다음과 같이 구현할 수 있다.

vector<vector<int>> linear_sieve(int n)
{
  vector<int> spf(n + 1);
  vector<int> prime_set;

  for (int i = 2; i <= n; ++i)
  {
    if (!spf[i])
    {
      prime_set.push_back(i);
      spf[i] = i;
    }

    for (int j = 0; (long long)i * prime_set[j] <= n; ++j)
    {
      spf[i * prime_set[j]] = prime_set[j];
      if (i % prime_set[j] == 0)
        break;
    }
  }

  return { prime_set, spf }; // 0: prime numbers, 1: spf
}

 

또한 이렇게 구한 spf 배열을 가지고 N 이하 자연수에 대해 $O(\log N)$의 시간 복잡도로 소인수 분해를 할 수 있음이 알려져 있다.

int x;
cin >> x;

vector<int> v;

while (x != 1)
{
  v.push_back(spf[x]);
  x /= spf[x];
}

 

오일러의 체는 에라토스테네스의 체보다 더 많은 역할을 할 수 있으니 구현법을 익혀놓는 것이 매우 도움이 될 것이다.

 

마지막으로 오일러의 체를 이용해 풀 수 있는 문제의 링크를 첨부하면서 게시글을 마친다.

 

https://www.acmicpc.net/problem/16563

16563번: 어려운 소인수분해

 

https://atcoder.jp/contests/abc215/tasks/abc215_d

D - Coprime 2