[BAEKJOON] 4134 다음 소수

📌 백준 13588번 - 다음 소수 (Next Prime)

Silver IV · 브루트포스 / 소수 판별

📋 문제 설명

🔍 문제 요약

정수 n (0 ≤ n ≤ 4×10⁹)이 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수를 출력하시오.

테스트 케이스 수 T가 첫 줄에 주어지고, 각 케이스마다 n이 한 줄씩 주어진다. n이 소수라면 n 그 자체가 정답, 아니라면 n+1부터 탐색해 나가면 된다.

💡 풀이 핵심 포인트

🤔 처음 접근 - 어떻게 소수를 판별할까?

가장 직관적인 방법은 2부터 N-1까지 모두 나눠보는 것인데, N이 최대 4×10⁹이라 이걸 그대로 쓰면 시간 초과가 난다.

소수 판별에서 핵심 수학적 사실이 있다.

N이 소수가 아니라면, N = a × b 인수분해에서 a, b 중 최소한 하나는 반드시 √N 이하다.

따라서 2 ~ √N 범위만 검사하면 충분하다. √(4×10⁹) ≈ 63,246 이므로 충분히 빠르다.

🤔 n = 0, 1은 어떻게 처리하지?

0과 1은 소수가 아니다. n이 0이나 1로 시작하면 루프를 돌기 전에 바로 2를 반환해야 한다. N <= 1 조건 하나로 처리하면 깔끔하다.

🤔 출력은 어떻게 빠르게 할까?

테스트 케이스가 많을 때 반복적으로 print() / println()을 호출하면 I/O 비용이 쌓인다. 결과를 모아두고 마지막에 한 번만 출력하는 게 성능에 유리하다.

🧩 알고리즘 설계

1. N <= 1이면 → 2 반환
2. 현재 N이 소수인지 판별 (2 ~ √N 순회)
3. 소수면 → N 출력
4. 소수가 아니면 → N++ 후 2번으로 돌아감

☕ Java 풀이

Java

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            long N = Long.parseLong(br.readLine());
            sb.append(nextPrime(N)).append("\n"); // 결과 누적 후 한 번에 출력
        }

        System.out.print(sb);
    }

    /** N 이상의 소수 중 가장 작은 소수 반환 */
    public static long nextPrime(long N) {
        if (N <= 1) return 2; // 0, 1은 소수가 아님

        while (true) {
            if (isPrime(N)) return N;
            N++;
        }
    }

    /** 소수 판별: 2 ~ √N 범위만 검사 */
    private static boolean isPrime(long N) {
        for (long i = 2; i <= Math.sqrt(N); i++) {
            if (N % i == 0) return false;
        }
        return true;
    }
}

⚠️ 기존 코드의 문제점

• primeNumber(N)을 루프 안에서 두 번 호출하는 버그 (불필요한 중복 연산)
• System.out.println()을 반복 호출하여 I/O 낭비

🐍 Python 풀이

Python

import sys
import math

input = sys.stdin.readline # 빠른 입력

def is_prime(n: int) -> bool:
    """n이 소수인지 판별한다. 2 ~ sqrt(n) 범위만 검사."""
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def next_prime(n: int) -> int:
    """n 이상의 소수 중 가장 작은 소수 반환."""
    if n <= 1:          # 0, 1은 소수가 아님
        return 2
    while True:
        if is_prime(n):
            return n
        n += 1

T = int(input())
result = []

for _ in range(T):
    N = int(input())
    result.append(next_prime(N))

# 결과 한 번에 출력 (반복 print 대비 성능 개선)
print("\n".join(map(str, result)))

🟨 JavaScript 풀이

JavaScript

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

/** n이 소수인지 판별: 2 ~ sqrt(n) 범위만 검사 */
function isPrime(n) {
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) return false;
    }
    return true;
}

/** n 이상의 소수 중 가장 작은 소수 반환 */
function nextPrime(n) {
    if (n <= 1) return 2; // 0, 1은 소수가 아님
    while (true) {
        if (isPrime(n)) return n;
        n++;
    }
}

const T = parseInt(input[0]);
const result = [];

for (let i = 1; i <= T; i++) {
    result.push(nextPrime(parseInt(input[i])));
}

// 결과 한 번에 출력
console.log(result.join("\n"));

⏱️ 시간복잡도 분석

소수 판별 1회: O(√N)
2부터 √N까지만 순회하므로 단일 소수 판별의 비용은 O(√N)이다.
N의 최댓값이 4×10⁹일 때, √(4×10⁹) ≈ 63,246번 연산으로 끝난다.

다음 소수까지 탐색: O(k × √N)
N이 소수가 아닐 경우 N+1, N+2, ... 순서로 탐색한다.
k를 "N에서 다음 소수까지의 거리"라 하면 전체 비용은 O(k × √N)이다.

💬 소수 간격(k)은 얼마나 될까?

정수론의 소수 정리(Prime Number Theorem)에 따르면, N 근방의 소수 간격은 평균적으로 ln(N)이다.
N = 4×10⁹일 때 ln(4×10⁹) ≈ 22이므로, 평균 22번 이내에 다음 소수를 찾는다.

전체 복잡도 요약

구분	복잡도	실제 최대 연산 수 (N = 4×10⁹)
소수 판별 1회	O(√N)	≈ 63,246
다음 소수 탐색	O(k × √N)	≈ 22 × 63,246 ≈ 1,391,412
테스트 케이스 T개	O(T × k × √N)	T에 비례

⚠️ 왜 에라토스테네스의 체를 쓰지 않았나?

체(Sieve)는 범위 내 모든 소수를 한 번에 구할 때 효율적이다.
하지만 이 문제는 N이 최대 4×10⁹이라 체를 만들려면 약 4GB 메모리가 필요해 메모리 초과가 난다.
따라서 각 케이스마다 개별 소수 판별(Trial Division)이 올바른 선택이다.

✅ 예제 검증

입력 N	소수 여부	탐색 과정	정답
6	❌ (2×3)	6→7 (소수!)	7
20	❌ (4×5)	20→21→22→23 (소수!)	23
100	❌	100→101 (소수!)	101

🔧 세 언어 공통 개선 요약

✔ 개선된 부분

• 소수 판별 분리: isPrime() 함수로 단일 책임 원칙 적용
• 출력 최적화: 반복 출력 대신 결과 모아서 한 번에 출력
• 엣지 케이스 단순화: N == 0 || N == 1 → N <= 1
• Java 버그 수정: primeNumber(N) 두 번 호출 → 한 번으로 수정
• 메서드명 명확화: primeNumber → nextPrime