Eratosthenes's Sieve

에라토스테네스의 체는 그리스의 수학자이자 천문학자이며 지리학자였던 에라토스테네스(B.C. 275 ~ 194)가 고안한, 소수를 찾아내는 방법이다.

에라토스테네스의 체는 임의의 자연수 n에 대하여 그 자연수 이하의 소수를 모두 찾아주는데, 그 과정을 알고리즘으로 나타내면 다음과 같다.

에라토스테네스의 체 알고리즘

1.  1부터 n까지의 자연수를 전부 나열한다.
2. 소수도, 합성수도 아닌 1을 지운다.
3. 남아 있는 자연수 중 가장 작은 수인 2는 소수다. 이제 2의 배수들을 모두 지운다.
4. 남아 있는 자연수 중 가장 작은 수인 3은 소수다. 이제 3의 배수들을 모두 지운다.
5. 남아 있는 자연수 중 가장 작은 수는 소수다. 이 수의 배수들을 모두 지운다.
6. 남은 자연수 중 가장 작은 수가 n의 제곱근을 넘을 때까지 과정 5를 반복하면, 남아 있는 수가 모두 소수다.

#include <iostream>
#include <math.h>
using namespace std;

#define MAX 100

int main()
{
    bool* isPrime = new bool[MAX];
    int squareRoot = (int)sqrt(MAX);

    //Eratosthenes's Sieve
    for (int i = 2; i < MAX; ++i) {
        isPrime[i] = (i & 1) != 0; // Multiples of 2 are false
    }

    isPrime[2] = true;

    for (int i = 3; i < squareRoot; i = i + 2) {
        if (isPrime[i] == false) {
            continue;
        }

        int num = i << 1; //if i is 3, then initial num value is 6

        while (num < MAX) {
            isPrime[num] = false;
            num = num + i;
        }
    }

    //result
    cout << "Prime :";
    for (int i = 2; i < MAX; ++i) {
        if (isPrime[i] == true) {
            cout << " " << i;
        }
    }
    cout << endl;

    delete(isPrime);

    return 0;
}