오일러의 체 (소수 구하기)

소수를 구하는 데에 있어 에라토스테네스의 체를 많이 사용하기도 한다.

에라토스테네스의 체란 

for(int i=2; i<=2000; i++){

if( sosu[i] ){

for(int j=2*i; j<=2000; j+=i){

sosu[j] = 0;

}

}

}

위와 같은 코드처럼 prime number로 저장된 녀석들이 range에 도달할 때까지의 (소수) x (어떤 수)를 하여 해당하는 수들을 모두 소수가 아닌 것으로 저장하는 것이다.

이 때 아이디어의 키포인트는, (소수) * (2이상 의 수)는 소수가 아니다라는 아이디어다

이를 반대로 생각해보면,

for(int i=2; i<RANGE; i++) {

if(!spf[i]) spf[i] = pr[pn++] = i;

for(int j = 0; i*pr[j] < RANGE; j++) {

spf[i*pr[j]] = pr[j];

if(i % pr[j] == 0) break;

}

}

(합성수) * (소수)는 소수가 아니다라는 순서를 바꿔서 알고리즘을 생각해보자.

spf[i] 가 i를 나누는  (합성수) * (소수)를 만족하는 최소의 소수 값이라 하고,

pr[i]는 i번째 소수라고 가정하자,

만약 i에 대해 spf[i] == 0 이라면, i는 소수이다. 

==> i가 2일 경우 spf[2] == 0 이기 때문에 , pr[0] = 2가 되는 것이다.

이 때, i에 대해 i * pr[0 ... j] ( for all j, such that i * pr[j] <= Range) 는, 합성수임을 만족하고,

spf[ i * pr[j] ] 는 pr[j]가 되는 것이다.  i가 합성수로 사용되고 pr[j]가 소수로 사용되었기 때문이다.

i % pr[j] == 0 일 경우 break가 되는 이유를 생각해보자.

먼저 i % pr[j] == 0 이라는 뜻은 i가 임의의 정수 k에 대하여, i = k * pr[j]를 만족하다는 것을 뜻한다.

여기서 break를 걸지 않는다면,

spf[i * pr[j+1] ] 에는 pr[j+1]이 들어가게 되는데, i % pr[j]를 만족하므로, spf[i * pr[j+1] ]에 pr[j]가 들어가야하는 것과 모순된다.

그렇기 때문에 i % pr[j] == 0일 경우 break를 걸어줘야 한다.

time complexity 는 O(n)이다. n개의 수에 대해 수를 나눌 수 있는 최소의 소수를 찾는 것인데,  n개의 수 자체 => O(n)이고, 최소의 소수를 찾는 과정을 전부 다 더해보면 O(n) 정도 되는 것 같다.

증명 방법은 모르겠다.