[백준 #4948] 베르트랑 공준 풀이

import java.util.Scanner;

public class Main {

    //  n > 123456 이므로 2n 은 최대 246912 이다.
    //	0 부터 시작하므로 246912 + 1
    
    public static boolean[] prime = new boolean[246913];

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        get_prime();  // 소수를 얻는 메소드 실행

        while(true) {
            int n = in.nextInt();
            if(n == 0) break;  // n 이 0 일경우 종료

            int count = 0;  // 소수 개수를 셀 변수

            for(int i = n + 1; i <= 2 * n; i++) {
                if(!prime[i]) count++;
            }
            System.out.println(count);
        }
    }

    // 소수를 얻는 메소드
    
    public static void get_prime() {
        // 0 과 1 은 소수가 아니므로 ture
        prime[0] = prime[1] = true;

        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) continue;
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

에라토스테네스의 체를 이용하여 boolean 배열로 소수인 경우는 false, 소수가 아닌 경우는 true를 담고 있도록 한다. 입력 N 이 주어지면 해당 배열에서 index 가 N ~ 2N 까지 순회하면서 false 의 개수를 세어준다.