소수 찾기 (에라토스테네스의 체)

소수 판별 알고리즘과 유사하지만, 목적이 다르다.

소수 판별은 특정 수가 소수인지 아닌지 찾아내는 알고리즘이라면,

소수 찾기는 주어진 범위 (0 ~ N)에 존재하는 소수를 찾아내는 알고리즘이다.

 

에라토스테네스의 체(Sieve of Eratosthenes)에 대한 내용은 여기로

 

위의 내용을 기반으로 작성된 코드이긴 하나, 약간의 최적화 과정을 거쳤다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    const int N = 30;
    vector<bool> A(N + 1, true);
    A[0] = A[1] = false;
    for(int i = 2; (i * i) < (N + 1); i++) //sqrt(N)까지만 진행
    {
        //A[i] == true 일 때만 진행한다
        //이미 지워진 수의 배수는 진행할 필요가 없다
        if (A[i])
        {
            // i * i 이전의 배수는 i보다 작은 소수의 배수이므로, 이미 지워져있다
            int k = i * i;
            
            while (k < (N + 1))
            {
                A[k] = false;
                k += i;
            }
        }
    }
    
    return 0;
}