Linear Sieve

Linear Sieve는 말 그대로 선형시간 $O(N)$에 소수 판별을 할 수 있는 알고리즘이다.

하지만 소수 판별 말고도 승법함수들을 $O(N)$에 덤으로 (?) 구하는것도 가능하기 때문에 쓸모가 많다. 아래 단락에서 살펴보자.

기존 에라토스테네스의 체는 $O(N \log\log N)$의 시간복잡도를 가지기 때문에 유의미한 시간복잡도 개선이 된다.

에라토스테네스의 체에서 합성수는 피치못하게 중복으로 검사가 된다.

$21=3 \cdot 7$ 이라는 수를 보면, $3$과 $7$모두 소수이기 때문에 $3,6,9,\dots$ 처럼 가는 과정과 $7,14,21,\dots$ 처럼 가는 과정에서 두 번 세진다.

따라서 $O(N)$의 시간복잡도가 나오지 못한다.

Linear Sieve는 이러한 문제를 해결한다.

원리

어떤 합성수 $x$를 $x=i \cdot p$ 라고 하자. $(p$는 소수이자 $x$의 최소 소인수$)$

$p$는 최소 소인수이기 때문에 $x=i \cdot p$에서 항상 $i \ge p$ 이다.

예를 들어, $21$의 최소 소인수 $p=3$ 이다.

어떤 합성수 $x$에 대해 $x$가 합성수다 라고 판단을 $x$의 최소 소인수인 $p$에서 단 한번만 이루어지게 하는 것이 핵심이다.

$x$에 집중하지 말고 $i$와 $p$에 집중한다.

$i$에 대해 반복문을 돌리며,

$(1)$ 현재 $i$가 아직 합성수라고 판단되지 않았다면 소수라고 판단한다.

$(2)$ 현재까지 검출된 소수 $p_j \le i$ 들에 대해서 작은 $p_j$ 부터, $i \cdot p_j$ 를 모두 살펴본다.

$x_j=i \cdot p_j$ 라 할 때, $x_j$의 최소 소인수는 $p_j$가 되는 것이다.

그런데 $x_j$가 이미 $i$에 대해 검사하기 전에 다른 $p < p_j$ 에 대해서 합성수라고 판단이 되어있을 수도 있지 않을까?

이런 상황을 방지하기 위해, $p_j \mid i$이면 $(2)$ 반복문을 종료한다.

$p_j \mid i$라는 것은 $p > p_j$ 인 $p$ 들에 대해서 $i \cdot p$의 최소 소인수가 $p$가 될 수 없기 때문이다.

$p_j \mid i$ 이기 때문에 $p_j \mid i \cdot p$ 이고 $p_j < p$ 라서 최소 소인수는 $p_j$ 이기 때문이다.

이런 과정을 거치면 의도대로 모든 합성수에 대해서 최소소인수 $p$들에 대해서 한 번씩만 검사가 되기 때문에 시간복잡도가 $O(N)$이 나온다.

구현

위 코드를 그대로 구현해보자.

const int N = 10000000;  
int min_prime_factor[N + 1];  
vector<int> primes;  
  
int cnt = 0; // debug count  
void linear_sieve() {  
   memset(min_prime_factor, -1, sizeof min_prime_factor);  
   for (int i = 2; i <= N; i++) {  
      if (min_prime_factor[i] == -1) {  
         min_prime_factor[i] = i;  
         primes.push_back(i);  
      }  
      for (int p: primes) {  
         cnt++; // debug count  
         ll x = i * p;  
         if (x > N) break;  
         min_prime_factor[x] = p;  
         if (i % p == 0) break;  
      }  
   }  
     
   cout << cnt; // 16034519  
}

$N=10,000,000$ 까지 검사했을 때, cnt 변수가 $16,034,519$이므로 거의 $O(N)$임을 볼 수 있다.

에라토스테네스의 체는 $29,465,738$ 회가 나왔다.

응용 1 - 소인수분해

$\sim N$ 까지의 수들에 대해 최소 소인수 배열을 구성한다면 빠르게 소인수분해를 할 수 있다.

왜냐면 최소 소인수들로 계속해서 나눠주기만 하면 되기 때문에 정확히 소수의 개수의 시간복잡도로 가능하다.

$O(1)$이라 보아도 무방

물론 Linear Sieve로만 최소 소인수 배열을 구성할 수 있는것은 아니다. 에라토스테네스의 체로도 가능하다.

void factorize(int x) {  
   while (x > 1) {  
      cout << min_prime_factor[x] << ' ';  
      x /= min_prime_factor[x];  
   }  
}

응용 2 - 승법함수

승법함수 는 다음과 같은 성질을 만족하는 수론 함수이다.

$n \perp m$이면 $f(nm)=f(n) \cdot f(m)$

대표적으로 상수함수, $\tau$(약수의 개수), $\sigma$(약수의 합), $\mu$(뫼비우스 함수), $\phi$(오일러 파이 함수) 등이 있다.

Linear Sieve가 에라토스테네스의 체랑 다르게 유용한 경우가 이러한 승법함수를 구성하는 데에 있다.

정수 $x$에 대해 $f(x)$를 구성하는 데 있어,

$x$가 $1$이나 소수라면

대개 성질을 이용해 빠르게 $f(x)$를 채워줄 수 있다.

$x$가 합성수라면

Linear Sieve의 원리를 생각해보면 $x=i \cdot p$처럼 합성수에 대해 단 한번만 최소 소인수로써 어떤 연산을 해줄 수 있는 구조이고 $i$는 소수이든 합성수이든 함수값들이 이미 구해져있는 상태이다.

$i \perp p$ 라면 편하게 $f(x)=f(i)f(p)$ 처럼 해줄 수 있지만, $p \mid i$ 인 경우도 존재한다.

이런 경우들은 함수의 성질과 관계식에 따라 알잘딱하게 처리해주면 된다.

직접 예시를 보자.

위에서 말한 $\tau$(약수의 개수), $\sigma$(약수의 합), $\mu$(뫼비우스 함수), $\phi$(오일러 파이 함수) 를 모두 Linear Sieve로 $O(N)$에 구해보도록 하자.

구현

$x=1$

$0$에 대해 항등적이 아닌 승법 함수들은 $f(1)=1$ 이다.

즉, $\tau(1)=\sigma(1)=\mu(1)=\phi(1)=1$ 로 초기화한다.

$x$는 소수

$p$가 소수일 때 $f(p)$ 들은 다음과 같다.

$\tau(p)=2$ $\because$ $1$과 자기 자신

$\sigma(p)=p+1$ $\because$ $1$과 자기 자신의 합

$\mu(p)=-1$ $\because$ $(-1)^r,~~(r=1)$ 이여서

$\phi(p)=p-1$

$x$는 합성수

$x$가 합성수일 때는 $x=i \cdot p$ 라 할 때, $p \mid i$ 인 경우와 $p \nmid i$ 인 경우를 나누어서 생각하자.

$p \nmid i$

이 경우 $gcd(p,i)=1$ 이기 때문에 $f(x)=f(i)f(p)$ 로 처리해준다.

$p \mid i$

$x=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$ 라 하자.

$\tau(x)$

$\tau(x)=(k_1+1)(k_2+1)\cdots (k_r+1)$ 이기 때문에 현재 $x$에 $p=p_1$가 얼마나 곱해져있는지 알면 된다.

이를 $c$ 라고 하자.

$x$가 소수거나 $p \nmid x$라면 $c(x)=1$ 이고, 그렇지 않다면 $c(x)=c(i)+1$ 이 될 것이다.

따라서 $\tau(x)=\dfrac {\tau(i)}{c(i)+1} \cdot (c(i)+2)$

$\sigma(x)$

$\sigma(x)=\dfrac {p_1^{k_1+1}-1}{p_1-1} \cdot \dfrac {p_2^{k_2+1}-1}{p_2-1} \cdots$

따라서

$$ \begin{aligned} \sigma(x)&=\sigma(i) \cdot \dfrac {p-1}{p_1^{c(i)+1}-1} \cdot \dfrac {p^{c(i)+2}-1}{p-1}\\ &=\sigma(i) \cdot \dfrac {p^{c(i)+2}-1}{p^{c(i)+1}-1} \end{aligned} $$

구현할 땐 오버플로우에 주의해야한다.

$\mu(x)$

$\mu$함수는 제곱인수가 포함되면 $0$이기 때문에 그냥 $\mu(x)=0$ 이다.

$p^2$ 를 인수로 가지게 되기 때문이다.

$\phi(x)$

$\phi(x)=\displaystyle \prod_{i=1}^r p_i^{k_i-1}(p_i-1)$

즉, $\phi(x)=\phi(i) \cdot p$

코드

const int N = 10000000;  
int min_prime_factor[N + 1], tau[N + 1], sigma[N + 1], mu[N + 1], phi[N + 1], c[N + 1];  
vector<int> primes;  
  
inline ll poww(ll a, ll b) {  
   ll ret = 1;  
   while (b) {  
      if (b & 1) {  
         ret *= a;  
      }  
      a *= a;  
      b >>= 1;  
   }  
   return ret;  
}  
  
void linear_sieve() {  
   memset(min_prime_factor, -1, sizeof min_prime_factor);  
  
   tau[1] = sigma[1] = mu[1] = phi[1] = 1;  
  
   for (int i = 2; i <= N; i++) {  
      if (min_prime_factor[i] == -1) {  
         c[i] = 1;  
         min_prime_factor[i] = i;  
         primes.push_back(i);  
  
         tau[i] = 2; // 소수의 약수의 개수: 1과 자기 자신  
         sigma[i] = i + 1; // 소수의 약수의 합: 1 + p  
         mu[i] = -1; // 소수의 서로 다른 소인수 개수: (-1)^1  
         phi[i] = i - 1; // 소수의 자신 이하에서 자신과 서로소인 개수: p - 1  
      }  
      for (int p: primes) {  
         ll x = i * p;  
         if (x > N) break;  
         min_prime_factor[x] = p;  
  
         if (i % p == 0) {  
            c[x] = c[i] + 1;  
  
            tau[x] = tau[i] * (c[i] + 2) / (c[i] + 1);  
            sigma[x] = sigma[i] * (poww(p, c[i] + 2) - 1) / (poww(p, c[i] + 1) - 1);  
            mu[x] = 0;  
            phi[x] = phi[i] * p;  
            break;  
         }  
         c[x] = 1;  
         tau[x] = tau[i] * tau[p];  
         sigma[x] = sigma[i] * sigma[p];  
         mu[x] = mu[i] * mu[p];  
         phi[x] = phi[i] * phi[p];  
      }  
   }  
}

참고

Comments

You may also enjoy