[백준] 4134 - JAVA

문제
정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력
각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

예제 입력 1

3
6
20
100

예제 출력 1

7
23
101

느낀점
초반에는 그저 에라토스테네스의 체를 이용해서 풀면된다고 생각하여 쉬운문제인줄 알았으나 생각보다 따져야할 것이 많았다. 또한 에라토스테네스의 체를 어떻게 코드로 짜는지 까먹어서 좀 슬펐다.

[출처: https://velog.io/@thsdnjst/Java-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4]

/*
소수 정리에 따르면
1. N이 충분히 큰 수라면 N 근처에 존재하는 소수들 사이의 평균 간격은 대략적으로 lnN이다
2. 어떤 큰 수 N에 가까운 정수 하나를 무작위로 고를때, 그 정수가 소수일 확률은 1/lnN에 근사
3. 소수의 분포는 더 큰 수로 갈수록 적어진다
*/

// "n이 소수인지 판별하려는 수 일때, n의 양의 제곱근 보다 작은 소수로 나누어 떨어지지 않으면 n은 소수이다."
// 따라서, 4*10^9 이상의 수에 대해 소수임을 판별하려면 sqrt(4*10^9) = 63,245 보다 작은 소수들로 나누자.
// 소수 정리에 따라 4*10^9 근처의 소수의 간격은 ln(4*10^9)이므로
// 즉 4*10^9이 소수가 아니라 해도 4*10^9 + ln(4*10^9) 이내에는 소수가 존재한다.
// 넉넉잡아 63,300 크기의 배열을 선언하자.
// static final int ARR_SIZE = 63300;
// static int[] primeNum = new int[ARR_SIZE];

위의 블로그에서 설명한것 처럼 먼저 가장 큰 소수를 미리 지정해놓고 소수와 비소수를 적어놓고 푸니 훨씬 더 빨리 풀린것 같다. 너무 정리를 잘해주셨다. 그저 실버를 다신 무시하지 않을 것이다.

코드

package baekjoon.algorithm.Problems.P4134;

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

public class Main {

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

        final int ARR_SIZE = 63300;
        int[] primeNum = new int[ARR_SIZE];

        int T;
        long n;
        boolean isPrime = false;

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

        for (int i = 0; i < ARR_SIZE; i++) {
            primeNum[i] = 1;
        }
        // 소수 배열 구하기 - 에라스토테네스의 체
        // 1이면 소수이고, 0이면 소수가 아니다.
        primeNum[0] = 0;
        primeNum[1] = 0;

        for (int i = 2; i < ARR_SIZE; i++) {
            for (int j = 2; i * j < ARR_SIZE; j++) {
                primeNum[i * j] = 0;
            }
        }

        // 입력 받은 수 n에 대하여 n보다 크거나 같은 소수 중 가장 작은 소수를 구해보자.
        T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            n = Long.parseLong(br.readLine());
            if (n <= 1) {
                System.out.println(2);
            } else {
                for (long i = n;; i++) {
                    int m = (int) Math.sqrt(i);
                    isPrime = true;
                    for (int j = 1; j <= m; j++) {
                        if (primeNum[j] == 1) {
                            if (i % j == 0) {
                                isPrime = false;
                                break;
                            }
                        }
                    }
                    if (isPrime) {
                        System.out.println(i);
                        break;
                    }
                }
            }
        }
    }
}