오일러의 체 (소수 구하기)
소수를 구하는 데에 있어 에라토스테네스의 체를 많이 사용하기도 한다. 에라토스테네스의 체란 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] =
