소수 구하기 1929

문제

접근 방법

에라토스테네스의 체를 활용하는 문제이다.
에라토스테네스의 체를 통해 소수가 아닌 것을 확인해 주고 소수인 것들만 출력하면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
int M, N;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> M >> N;
    vector<bool> isNotPrime(N + 1);
    isNotPrime[1] = true;
    for (int i = 2; i * i <= N; ++i)
        if (!isNotPrime[i])
            for (int j = i * i; j <= N; j += i)
            {
                isNotPrime[j] = true;
            }
    while (M <= N)
    {
        if (!isNotPrime[M])
            cout << M << "\n";
        ++M;
    }
    return 0;
}

풀이

범위가 정해졌다면 하나씩 확인하는 것보다 체에 걸러서 확인하는 것이 좋다.