1929번

1929번 - 소수 구하기

에라토스테네스의 체를 이용해서 소수를 구했다.

에라토스테네스의 체는 원하는 범위에서의 모든 소수를 구하고 싶을 때, 배수를 체크해가면서 남은 소수를 찾아가는 방법이다.

기존에 소수를 구하던 방법 보다 소수를 더 빠르게 구할 수 있다는 장점이 있다.

백준 강의를 들을 때 안쪽 for 문에서 j = i * i 로 구현하면 더 빠르겠지만, n제한이 100만 일경우에는 j = i * 2 로 구현한다고 하였다.

i * i 가 좀 더 빠르겠지만, 귀찮게 조건을 살펴야 하느니 i * 2 로 사용해야겠다. 

< 정답 코드 >

#include<iostream>
#include<vector>
using namespace std;
 
bool check[1000001];
 
 
int main()
{
    int N, M;
    cin >> N >> M;
 
    for (int i = 2; i <= M; i++)
    {
        if (!check[i])
        {
            if (i >= N)
            {
                cout << i << endl;
            }
 
            for (int j = i*2; j <= M; j += i)
            {
                check[j] = true;
            }
        }
 
    }
 
    return 0;
}