백준 1929

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int M, N;
    cin >> M >> N;
    
    bool isPrime[N+1];
    fill_n(isPrime, N+1, true);
    isPrime[1] = false;
    
    int sqr = (int)sqrt(N);
    
    for(int i=2; i<=sqr; i++) {
        
        if(isPrime[i]) {
            for(int j=2; i*j<=N; j++) {
                isPrime[i*j] = false;
            }
        }
    }
    
    for(int i=M; i<=N; i++) {
        if(isPrime[i])
            cout << i << '\n';
    }
    
    return 0;
}

설명

보완점

j=2 대신에 딱 필요한 부분인 M부터만 계산하고 싶은데 잘 안된다. 나중에 시도해보자.