[백준 4948] 베르트랑 공준

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

https://pushback.tistory.com/8

소수 문제 해결의 기본

---

 \(n\)의 범위가 \(1 \leq n \leq 123,456\)이므로, 에라토스테네스의 체로 해결하는게 가장 빠른 시간안에 해결할 수 있을 것으로 보인다. 에라토스테네스의 체를 사용해보자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 123457 * 2;
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));

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

    while (true) {
        int n, cnt = 0;
        cin >> n;
        if (n == 0) break;
		
        for (int i = n + 1; i <= 2 * n; i++) {
            if (isPrime[i]) {
                cnt++;
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}