BOJ) 베르트랑 공준

베르트랑 공준

4948번: 베르트랑 공준

풀이

 

에라토네스의 채를 확실히 익혔는지 확인하려고 풀었다.

방법은 바로 이전 포스팅과 같기 때문에 딱히 포스팅할 말은 없다.

 

에라토네스 채는 자신의 배수에 대해서 소수가 아님을 체크해주는 방식이다.

 

코드

 

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

public class FindPrimeNums_4948 {
    final static String END = "0";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = "";

        while(!(inputStr = br.readLine()).equals(END)) {
            int n = Integer.parseInt(inputStr);
            System.out.println(getCnt(n));
        }
    }

    private static int getCnt(int n) {
        int cnt =0;
        boolean[] prime = new boolean[n*2+1];

        for(int i=2; i<=2*n; i++) {
            if(!prime[i]) {
                if(i >n) {
                    cnt++;
                }
                for(int j=i*2; j<=2*n; j+=i) {
                    prime[j] = true;
                }
            }
        }
        return cnt;
    }
}