[백준] 4948번: 베르트랑 공준

n보다 크고 2n보다 작거나 같은 숫자 중에서 소수의 갯수 구하기
1 <= n <= 123456
n보다 크다 = n+1
2n보다 작거나 같다 = 123456 * 2

16의 경우 약수를 p*q 부등식인 4*4로 표현할 수 있는데 다음으로 큰 수를 표현하면 8*2
그렇다면 p와 q 중 하나는 반드시 제곱근 n보다 작거나 같다.
즉, 제곱근 n이하의 자연수 중에 나누어 떨어지는 수가 있다면 1과 n을 제외한 약수가 있다는 의미
= 소수가 아니게 되는 것
제곱근 n이하의 수를 검사하면 시간복잡도는 OlogN

에라토스테네스의 체를 이용하여 배수 제거하였다.

 

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

public class Main {
    static boolean[] primeArr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        isPrime();
        int num = -1;
        while ((num = Integer.parseInt(br.readLine())) != 0) {
            int cnt = 0;
            for(int i=num+1; i<=2*num; i++) {
                if(!primeArr[i]) cnt++;
            }
            sb.append(cnt).append("\n");
        }
        System.out.print(sb);
    }
    public static void isPrime() {
        primeArr = new boolean[123456 * 2 + 1];
        primeArr[0] = primeArr[1] = true;
        //Math.sqrt: 제곱근 구하기
        for(int i=2; i<=Math.sqrt(primeArr.length); i++) {
            if(primeArr[i]) continue;
            for(int j=i*i; j<primeArr.length; j = j+i)
                primeArr[j] = true;
        }
    }
}