BOJ - 베르트랑 공준(4948)

실버2 : 수학 문제이다.

생각

소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAX 123456*2
using namespace std;
int N;
 
bool isPrime[MAX+1];
 
void SeiveofEratosThenes(){
    fill(isPrime+2, isPrime+MAX+1, true);
    for (int i = 2; i*i <= MAX; i++) {
        if (isPrime[i] == false) continue;
        for (int j = i*i; j <= MAX; j+=i) {
            isPrime[j] = false;
        }
    }
}
 
int main(){
    SeiveofEratosThenes();
 
    while (1) {
        int count = 0;
        cin >> N;
        if (N == 0) {
            break;
        }
        for (int i = N+1; i <= 2*N; i++) {
            if (isPrime[i]) count++;
        }
        cout << count << '\n';
    }
 
    return 0;
}
 

Reference

• 백준(4948번) - 베르트랑 공준