백준 4948번: 베르트랑 공준

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

유사 문제 참고: http://qlyh8.tistory.com/144?category=731166

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {    
    public static void main(String[] args) throws Exception {
        int endNum = 123456*2+1;
        boolean[] isPrimeArr = new boolean[endNum];
        Arrays.fill(isPrimeArr, true);
        isPrimeArr[0] = false;
        isPrimeArr[1] = false;
        
        for(int i=2 ; i<=(int)Math.sqrt(endNum) ; ++i) {
            if (isPrimeArr[i]){
                for (int j=i+i; j<=endNum; j+=i)
                    isPrimeArr[j] = false;
            }
        }
        
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        
        while(true){
            int n = Integer.parseInt(reader.readLine());
            if(n == 0)
                break;
            
            int count = 0;
            for(int i=n+1 ; i<=n*2 ; i++){
                if(isPrimeArr[i])
                    count++;
            }
            builder.append(count).append("\n");
        }
        
        System.out.println(builder);
    }
}