[백준 4948] 베르트랑 공준

문제 : https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

앞서 풀었던 소수 문제랑 동일하게 에라토스테네스의 체를 이용하여 소수들을 미리 구해놓은 뒤 

소수의 개수를 카운트 해주었다.

 

관련 문제 : 2019/08/05 - [PS/백준 문제풀이] - [백준 2581] 소수

 

 

 
#include <iostream>
#include <cmath>
using namespace std;
 
int n;
bool isNotPrime[123456*2+1];
 
void eratos(){
    // 1은 소수가 아님을 처리안해줘서 처음에 틀림
    isNotPrime[1] = true;
    int maxi = sqrt(123456*2);
    for(int i = 2; i <= maxi; i++){
        if(!isNotPrime[i]){
            for(int j = i*i; j <= 123456*2; j += i)
                isNotPrime[j] = true;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    eratos();
    
    while(1){
        cin >> n;
        if(n == 0)
            break;
        
        int count = 0;
        for(int i = n+1; i <= 2*n; i++){
            if(!isNotPrime[i]){
                count ++;
            }
        }
        cout << count << '\n';
    }
    
    return 0;
}