[java] 백준 4134 다음 소수

이 문제는 주어진 값에 대해 크거나 작은 수 중 가장 가까운 소수를 수하는 문제이다.

 

제한시간이 1초인 문제이기 때문에 반복문의 범위가 굉장히 중요한 것으로 생각된다.

 

주의할 점은 입력받은 수의 크기가 최대 40억이기 때문에 int대신 long타입을 써야한다.

 

소수인지 판별해 알려주는 isPrime메소드를 만들었다.

 

소수면 true, 아니면 false를 반환한다.

 

2보다 작은 값은 소수가 아니기 때문에 false를 반환한다. 

 

소수가 아닌 숫자들은 해당 수의 제곱근보다 작거나 같은 값을 무조건 약수로 가진다. 따라서 반복문 범위를 제곱근까지만 해도 

 

해당 수가 소수가 아닌 것을 판별할 수 있다(제곱근보다 작거나 같은 수로 나누어 진다면).

 

가장 가까운 소수를 출력해야 하기에 0, 1에 대해 2로 출력하는 에외처리를 해주었다.

 

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

public class Main {
    public static void main(String[] args) throws Exception {

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

        int N = Integer.parseInt(br.readLine());
        // 테스트 케이스 개수

        for (long i = 0; i < N; i++) {
            long n = Long.parseLong(br.readLine());
            // 테스트케이스 입력
            
            for (long j = n; j <= Long.MAX_VALUE; j++) {
                if (j == 0) {
                    System.out.println(2);
                    break;
                    //0을 입력받는다면 가장 가까운 소수 2를 출력
                } else if (j == 1) {
                    System.out.println(2);
                    break;
                    // 1을 입력받는다면 가장 가까운 소수 2를 출력
                }
                if (isPrime(j)) {
                    System.out.println(j);
                    break;
                    
                    // 이외에는 소수라면 해당 수를 출력함.
                }

            }
        }

    }

    public static boolean isPrime(long num) {
        if (num < 2) {
            return false;
            // 2보다 작은 값은 소수
        }
        
        for (long i = 2; i <= Math.sqrt(num); i++) {
        	//반복문 범위를 줄이기 위해 제곱근을 가져오는 Math.sqrt사용
            
            if (num % i == 0) {
            	//반복문을 통해 2부터 제곱근 까지 차례대로 나누어 나누어지는 값이 있으면 false출력 
                return false;
            }
        }

        return true;
    }
}