소수 찾기 - 에라토스체네스 체

소수가 아닌 수들은 반드시 다른 소수로 나누어진다는 사실에 기반해서 동작한다.

 

처음 주어진 리스트는 1부터 max까지의 모든 수로 구성되어 있다.

• 처음에는 2로 나누어지는 모든 수를 리스트에서 없앤다.
• 그 후 다음 소수, 즉 아직 지워지지 않은 수 중 가장 작은 수를 찾는다.
• 그리고 그 수로 나누어지는 모든 수를 리스트에서 제거한다. 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
void crossOff(vector<bool>& flags, int prime)
{
    /* prime의 배수들을 제거해나간다. k < prime 인 k에 대한 k * prime은
    이전 루프에서 이미 제거되었을 것이므로 prime * prime부터 시작한다. */
    for (int i = prime * prime; i < (int)flags.size(); i += prime)
    {
        flags[i] = false;
    }
}
 
int getNextPrime(vector<bool>& flags, int prime)
{
    int next = prime + 1;
    while (next < (int)flags.size() && !flags[next])
    {
        next++;
    }
    return next;
}
 
vector<bool> sieveOfEratosthenes(int max)
{
    vector<bool> flags(max+1);
    int count = 0;
 
    /* 0, 1 번 인덱스를 제외하고 모두 초기화*/
    for (int i = 0; i < (int)flags.size(); i++)
    {
        if (i == 0 || i == 1)
        {
            flags[i] = false;
        }
        else
        {
            flags[i] = true;
        }
    }
 
    int prime = 2;
 
    while (prime <= sqrt(max))
    {
        /* prime의 배수들을 지워나간다. */
        crossOff(flags, prime);
 
        /* 그다음 true로 세팅된 인덱스를 찾는다. */
        prime = getNextPrime(flags, prime);
    }
    
    return flags;
}
 
int main()
{
    int max = 25;
    vector<bool> result = sieveOfEratosthenes(max);
 
    for (int i = 2; i < (int)result.size(); i++)
    {
        if (result[i] == true)
        {
            cout << i << " : 소수" << endl;
        }
        else
        {
            cout << i << "  :  X" << endl;
        }
    }
 
    return 0;
}