[백준 문제 풀이] 4134번 다음 소수

Junu Kim·2026년 1월 3일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

82/89

[4134] 다음 소수

난이도: ★★☆☆☆ • solved on: 2026-01-03

문제 요약

문제 유형: 수학, 소수 판정, 브루트포스
요구사항: 각 테스트케이스마다 입력된 수 n 이상에서 가장 작은 소수를 찾아 출력해야 한다.

사용 개념

자료구조
- StringBuilder : 여러 줄 출력 누적
- BufferedReader : 빠른 입력
알고리즘/기법
- 소수 판정(Prime Check)
- n부터 1씩 증가시키며 첫 소수 탐색
핵심 키워드
- 소수(prime number)
- √n 까지 나눗셈 검사

풀이 아이디어

문제 분해

각 입력 target에 대해 current = target으로 시작한다.

current가 소수인지 확인하고, 아니면 current++ 하며 반복한다.

처음으로 소수 판정을 통과한 current를 출력한다.
핵심 로직 흐름
for i in 1..T:
    current = target
    while true:
        if isPrime(current):
            print current
            break
        current++
예외 처리

0, 1은 소수가 아니므로 false로 처리한다.

2는 소수이므로 true로 처리한다.

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long target;
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < n; i++){
            String s = br.readLine();
            target = Long.parseLong(s);
            long current = target;
            while(true){
                if(isPrime(current)){
                    sb.append(current).append("\n");
                    break;
                }
                current++;
            }
        }
        System.out.print(sb);
    }
    public static boolean isPrime(long n){
        if(n == 1 || n == 0) return false;
        if(n == 2) return true;
        for(long i = 2; i*i <= n; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}