백준(BOJ)_소수 구하기(1929번)_C++

에라토스테네스의 체를 이용해 1,000,000 이하의 자연수에 대해 소수 판별을 미리 진행하면

m과 n에 상관없이 빠른 시간복잡도로 문제를 해결할 수 있다.

 

#include <iostream>

using namespace std;

int m, n;
bool is_not_prime[1000001];

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> m >> n;

    //check prime number
    is_not_prime[1] = true;
    for(int i = 2; i <= 1000000; i++)
        if (is_not_prime[i] == false)
            for(int j = i * 2; j <= 1000000; j += i)
                is_not_prime[j] = true;

    //output
    for(int i = m; i <= n; i++)
        if (is_not_prime[i] == false)
            cout << i << "\n";
}