[백준 4948] 베르트랑 공준

 

1929번 문제를 풀때와 마찬가지로 소수를 제거하고 n<k<=2n 를 만족하는 소수의 개수를 구한다.

 

 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int prime[] = new int[246913];
        for(int i=0; i<prime.length; i++)
            prime[i] = 1;
        prime[1] = 0;
        
        for(int i=2; i<=123456; i++) {
            for(int j=2; i*j<=prime.length; j++) {
                prime[i*j] = 0;
            }
        }
        
        while(true) {
            int n = sc.nextInt();
            if(n == 0) break;
            
            int cnt = 0;
            for(int i=n+1; i<=2*n; i++) {
                if(prime[i] == 1)
                    cnt++;
            }
            System.out.println(cnt);
        }
        
        sc.close();
}