[JAVA] 백준 베르트랑 공준 4948

조건 : n보다 크고 2n보다 작거나 같은 소수는 적어도 하나 존재한다.

소수 문제는 무조건 : 에라토스테네스의 체를 사용하자!

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n==0){
                break;
            }

            System.out.println(estorane(2*n));
        }
    }

//에스토라네의 체를 통해 배열을 만들고
// 범위내의 소수들을 찾아서 리턴
    private static int estorane(int n) {
        int arr[] = new int[n+1];
        //0 1 2 3 4 5 6 7 8 9 10
        arr[1] = 1;
        for(int i =2; i<=Math.sqrt(n); i++){
            if(arr[i]==0) {
                for (int j = i; i*j<n+1; j++) {

                    arr[i * j] = 1;
                }
            }
        }
        int count = 0;
        for(int i =n/2+1; i< arr.length; i++){
            if(arr[i] == 0){
                count++;
            }
        }
        return count;

    }


}