[백준 1929] 소수 구하기

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

소수 문제 해결의 기본

---

 

 입력의 범위가 \( 1 \leq M \leq N \leq 1,000,000\) 이므로 숫자 하나하나를 naive한 방법이나 naive하게 \(\root N\)까지 보는 방법으로 소수를 판별해서 시간 안에 통과하기는 쉽지 않아 보인다. 따라서 에라토스테네스의 체를 쓰자.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 10e+6 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isPrime[MAX_N];

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(isPrime, 1, sizeof(isPrime));

    int M, N;
    cin >> M >> N;

    isPrime[1] = false;
    for (int i = 2; i <= N; ++i) {
        if (isPrime[i]) {
            for (ll j = i * 1LL * i; j <= (ll) N; j += i * 1LL) {
                isPrime[j] = false;
            }
        }
    }

    for (int cur = M; cur <= N; ++cur) {
        if (isPrime[cur]) {
            cout << cur << '\n';
        }
    }

    return 0;
}

한가지 재미있는 점은 isPrime 배열을 매번 1,000,000개에 대해 초기화 해주면 아래와 같이 64ms이 걸리고,

위 코드와 같이 N의 범위에 맞춰서 초기화 해주면 16ms가 걸린다.