가성비 에라토스테네스의 체

에라토스테네스의 체에서 간단한 최적화만으로도 매우 빠르게 동작합니다. $O(N \log \log N)$ 시간복잡도를 가졌지만, 로컬에서 1억에 0.25초, 10억에 3.6초 정도에 동작합니다.

 

vector<bool> p(N + 1);
p[2] = true;
for (uint64_t i = 3; i <= N; i += 2)
    p[i] = true;
for (uint64_t i = 3; i * i <= N; i += 2)
    if (p[i])
        for (uint64_t j = i * i; j <= N; j += 2 * i)
            p[j] = false;

기본적인 에라토스테네스의 체와 같은 방식으로 처리합니다. 단, 다음과 같은 최적화를 거쳐줍니다.

• 1번 줄: vector<bool>은 필수적입니다. 라이브러리가 bit단위로 값을 저장하기 때문에, 메모리 사용량을 획기적으로 줄일 수 있습니다. (수 800만개당 1MB입니다. 1억은 12.5MB, 10억은 125MB를 사용합니다)
• 2-4번 줄: 소수가 될 수 있는 수는, 3 이상의 홀수와 2 뿐입니다.
• 5번 줄 (i=3, i+=2): 2의 배수는 이미 불가능하다고 체크했기 때문에, 3이상의 홀수에 대해서만 순회합니다.
• 7번 줄
  • j = i*i: i*i 미만의 i의 배수는 i보다 작은 다른 소인수를 가지고 있어서 이미 체크가 되어있으므로, 무시해도 됩니다.
  • j += 2*i: 홀수인 j만 고려하면 되기 때문에, j를 2*i씩 건너뜁니다.
• 5번 줄 (i*i <= N): i*i > N 인 경우 7번 줄에 해당하는 for문이 아예 실행되지 않습니다.