1929번: 소수 구하기

알고리즘 분류를 보기 전까지 한참 해맸다.

시간초과를 해결하는 게 관건인데

에라토스테네스의 체를 이용해 해결할 수 있다.

#include <iostream>
    
int check[1000001] = { 0 };
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int min, max;
    std::cin >> min >> max;
 
    check[1] = 1;
    for (int i = 2; i <= max; i++) {
        int cur = i;
        int count = 2;
        while (cur * count <= max) {
            check[cur * count] = 1;
            count++;
        }
        if (!check[i]) {
        }
    }
 
    for (int i = min; i <= max; i++) {
        if (check[i]) continue;
        std::cout << i << "\n";
    }
 
    return 0;
}