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

진행 과정

순차 탐색 -> 색칠되지 않은 칸 발견 -> 해당 칸을 소수로 분류하고, 해당 숫자의 곱을 모두 색칠.

 

코드

#include <iostream>
using namespace std;
 
bool Num[1000001] = {};
 
int main()
{
    int Start, End;
    cin >> Start >> End;
    
    for (int i = Start ; i <= End; ++i)
        if(!Num[i])
            for (int j = 2; j*i <= End; ++j)
                    Num[i * j] = true;
}

(Start != 1)일때, Start ~ End 까지의 소수를 판별해주는 코드. Num[i]가 false인 칸이 소수이다.