백준 9단계(4948)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    
    //1
    //10
    //13
    //100
    //1000
    //10000
    //100000
    //0
    
    //result
    
    //1
    //4
    //3
    //21
    //135
    //1033
    //8392
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        //n이 0이 입력될때까지 반복 처리
        int n;
        while((n = Integer.parseInt(br.readLine())) != 0){
            
            //sieve of eratosthenes
            boolean[] bool = new boolean[2 * n + 1];
            for(int i = 1; i < bool.length; i++) {
                bool[i] = true;
            }
            
            for(int i = 2; i < Math.sqrt(bool.length) ; i++) {
                if(bool[i]) {
                    for(int j = i * i; j < bool.length; j += i) {
                        bool[j] = false;
                    }
                }
            }
            //시작 번호 + 1을해서 처리를 해야한다, 그 이유는 13을 입력했을때 
            //시작 번호를 포함하면 4개 소수이지만 포함을 안하면 3개 소수를 출력한다
            int cnt = 0;
            for(int i = n + 1; i <= 2*n; i++) {
                if(bool[i]) cnt++;
            }
            bw.write(String.valueOf(cnt) + "\n");
            
        }
        bw.flush();
    }
    
}