[백준] 다음 소수 (4134번)

코드 힌트

1. 목표:
   • 주어진 숫자 target에서 시작해, 가장 가까운 소수를 찾는 문제입니다.
   • 입력으로 주어진 숫자들 각각에 대해 처리합니다.
2. 소수 판별:
   • n이 소수인지 확인하기 위해, 2부터 Math.sqrt(n)까지의 범위에서 나누어 떨어지는지 검사합니다.
   • 이 과정에서 n이 1보다 작거나 2 또는 3일 때의 특별한 경우를 처리합니다.
3. 소수 찾기:
   • target이 소수가 아닌 경우, target을 1씩 증가시키며 소수를 찾습니다.
   • 소수를 찾으면 현재 target 값을 출력합니다.
4. 효율적인 소수 판별:
   • Math.sqrt(n)을 사용하여 제곱근까지만 검사하여 소수 판별을 최적화합니다.
   • 반복문을 사용하여 소수를 찾을 때, target을 증가시켜가며 검사합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // 입력 받을 숫자의 개수
        int n = Integer.parseInt(in.nextLine());
        
        // n개의 숫자에 대해 처리
        for (int i = 0; i < n; i++) {
            // 각 숫자를 읽어오기
            long target = Long.parseLong(in.nextLine());
            
            // 타겟 숫자가 소수가 될 때까지 반복
            while (true) {
                // 현재 타겟 숫자가 소수인지 확인
                if (isPrime(target)) {
                    break; // 소수이면 반복 종료
                }
                target++; // 소수가 아니면 1씩 증가
            }
            
            // 소수가 된 타겟 숫자를 출력
            System.out.println(target);
        }
    }
    
    // 주어진 숫자가 소수인지 판별하는 메소드
    public static boolean isPrime(long n) {
        // 숫자가 1 이하일 때는 소수가 아님
        if (n <= 1) return false;
        // 2와 3은 소수
        if (n == 2 || n == 3) return true;
        
        // 2와 3 외의 숫자에 대해 제곱근까지 나누어 떨어지는지 확인
        for (int j = 2; j <= (int) Math.sqrt(n); j++) {
            if (n % j == 0) return false; // 나누어 떨어지면 소수가 아님
        }
        
        // 위의 조건을 모두 통과하면 소수
        return true;
    }
}