Baekjoon 4948. 베르트랑 공준 / Java

알고리즘 설명

문제 설명

임의의 자연수 n에 대하여 n보다 크고 2n보다 작은 소수가 적어도 하나 존재한다.
n보다 크고 2n보다 작은 소수의 개수를 구하는 문제

알고리즘 설명

1. isPrime : n의 최댓값 * 2 까지 소수판별을 한다. 이 때, 에라토스테네스의 체를 사용한다. 시간복잡도 : O(n log n)
2. countPrime배열에 소수 개수를 저장한다. 시간복잡도 O(n)

import java.io.*;

public class Main {
    public static int n;
    // 소수 판별 배열, true이면 소수가 아님
    public static boolean[] isPrime = new boolean[123456 * 2 + 1];
    // 소수 개수를 누적합으로 저장하는 배열
    public static int[] countPrime = new int[123456 * 2 + 1];

    public static void main(String[] args) throws IOException {

        sol();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }
            // n보다 크고 2n보다 작거나 같은 소수의 개수를 출력
            System.out.println(countPrime[2 * n] - countPrime[n]);
        }
    }

    // 소수와 소수 개수 배열을 초기화하는 함수
    private static void sol() {
        // 0과 1은 소수가 아님
        isPrime[0] = true;
        isPrime[1] = true;
        // 에라토스테네스의 체 알고리즘을 사용하여 소수를 판별
        for (int i = 2; i <= Math.sqrt(123456 * 2); i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= 123456 * 2; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        // 소수 개수 배열 초기화
        countPrime[0] = 0;
        countPrime[1] = 0;
        // 소수 개수를 누적합으로 계산
        for (int i = 2; i <= 123456 * 2; i++) {
            if (!isPrime[i]) {
                countPrime[i] = countPrime[i - 1] + 1;
            } else {
                countPrime[i] = countPrime[i - 1];
            }
        }
    }
}