에라토스테네스의 체

에라토스테네스의 체

 

2부터 시작해서 자기자신을 제외한 n의 배수를 전부 체크하고

체크되지 않은 것들이 소수가 되는 알고리즘이다.

vector<int> v(n + 1);

for (int i = 2; i < n + 1; ++i)
{
    for (int k = 2 * i; k < n + 1; k += i)
        ++v[k];
}

vector<int> prime;
for (int i = 2; i < n + 1; ++i)
{
    if (v[i] == 0)
        prime.emplace_back(i);
}

 

1은 소수가 아니라는점에 주의하자.

 

따라서 [0] 번 위치와 [1] 위치는 소수가 아니므로 [2] 위치부터 소수이다.

 

 

구하려는 수가 충분히 작은 경우에는 최적화를 할 수 있는데,

예를들어 4를 검색할 때는 이미 2에서 제외된 로직을 다시 실행하는 꼴이 되므로

n * n + n * i 꼴로 실행하면된다.

 

하지만 n의 제공이 int 범위를 넘는 경우가 많으므로 많은 경우에서는 쌩으로 구하는게 맞다.

vector<int> v(n + 1);

for (int i = 2; i < n + 1; ++i)
{
    for (int k = i * i; k < n + 1; k += i)
    {
        cout << k << "삽입" << " I : " << i << endl;
        ++v[k];
    }
}

vector<int> prime;
for (int i = 2; i < n + 1; ++i)
{
    if (v[i] == 0)
        prime.emplace_back(i);
}