4134번 다음 소수 문제: 뇌를 쥐어짜는 소수 판정의 여정

오늘은 정말이지 뇌를 쥐어짜는 경험을 했다. 알고리즘 문제 4134번, '다음 소수 찾기'를 푸는 과정에서 소수 판정의 기초부터 현대 알고리즘의 필요성까지, 깊은 곳까지 파고들었다. ChatGPT와의 대화를 통해 이론적인 이해를 넘어, 실제 코딩에서 마주치는 함정들과 최적화의 중요성을 뼈저리게 느낄 수 있었다.

학습 주제

오늘 공부한 주제: "다음 소수 찾기" 알고리즘 문제 (4134번)
대화 제목: 소수 판정법 이론
학습 날짜: 2026년 2월 3일

질문과 탐구

모든 것은 "N 이상의 가장 작은 소수를 찾아라"는 문제 정의에서 시작되었다. 직관적으로는 N부터 시작해서 하나씩 증가시키며 소수인지 판별하면 될 것 같았다. 하지만 곧이어 발생하는 의문은 다음과 같았다.

어떤 수까지 검사해야 소수인지 판정할 수 있을까? (핵심: $n$ 까지만 검사하면 된다는 이론)
$n$ 까지 검사할 때, 모든 수를 다 검사해야 할까, 아니면 소수만 골라서 검사해도 될까?
내 코드가 왜 시간 초과가 나는 걸까? (이론은 맞는데…?)
이론과 구현의 괴리가 이렇게 클 수 있나?

이 질문들을 따라가면서, 단순한 소수 판정법을 넘어 알고리즘 설계의 깊은 곳으로 빠져들었다.

핵심 학습 내용

ChatGPT와의 대화를 통해 소수 판정법의 핵심 원리를 다시 한번 다질 수 있었다.

1. 소수의 정의와 기본 판정법

소수는 1과 자기 자신만을 약수로 가지는 자연수라는 기본적인 정의에서 시작한다. 가장 단순한 판정법은 2부터 $n - 1$ 까지 모든 수로 나누어보는 것이다.

2. $n$ 까지만 검사해도 충분한 이유

약수가 $a \cdot b = n$ 일 때, $a$ 와 $b$ 둘 중 하나는 반드시 $n$ 이하라는 점을 이용하면 검사 횟수를 획기적으로 줄일 수 있다.

n = 36
약수 쌍: (1,36), (2,18), (3,12), (4,9), (6,6), (9,4), (12,3), (18,2), (36,1)
                     ↑
                 √36 = 6

√n 까지만 검사하면 충분한 이유:
- 6보다 작은 약수들은 모두 쌍으로 6보다 큰 약수와 연결됨
- 예: 2 → 18, 3 → 12, 4 → 9, 6 → 6
- √n 이후는 이미 앞에서 확인한 약수의 쌍이므로 중복 확인 필요 없음

3. C++ 구현 시의 함정과 최적화

초기 코드에서는 $n$ 과 $i$ 를 혼동하거나, passCnt 같은 비효율적인 로직을 사용하는 등 여러 오류를 범했다. 특히 break 문이 if 블록에 제대로 묶이지 않아 무한 루프에 빠지거나, sqrt() 함수 대신 d*d <= n을 사용하는 것이 연산 속도와 정확성 면에서 훨씬 유리하다는 것을 배웠다.

// 비효율적인 passCnt 로직 (초기 코드)
passCnt++;
if (passCnt == (int)sqrt(n) - 1) {
    cout << n << '\n';
    break;
}

// 최적화된 소수 판정 로직 (이론)
bool isPrime = true;
if (n < 2) isPrime = false; // 1은 소수 아님
for (long long d = 2; d * d <= n; d++) { // d*d <= n 사용
    if (n % d == 0) {
        isPrime = false;
        break;
    }
}
if (isPrime) {
    cout << n << '\n';
    break; // 정답 찾으면 루프 탈출
}

4. 4×10⁹ 범위에서의 최적화: 홀수만 검사

$n$ 이 2보다 큰 짝수라면 무조건 소수가 아니라는 점을 이용해, 2를 제외한 모든 소수 판정에서는 3부터 시작하여 2씩 증가시키며 홀수만 검사하는 것이 효율적이다.

// 홀수만 검사하는 최적화
bool isPrime(ll n){
    if(n < 2) return false;
    if(n == 2) return true; // 2는 예외 처리
    if(n % 2 == 0) return false; // 2보다 큰 짝수는 소수 아님

    for(ll d = 3; d*d <= n; d += 2){ // 3부터 시작, 2씩 증가
        if(n % d == 0) return false;
    }
    return true;
}

5. 4134번의 실제 함정: 에라토스테네스의 체와 반복 횟수

처음에는 $N$ 부터 시작해서 isPrime 함수를 계속 호출하며 다음 소수를 찾는 방식이 효율적일 줄 알았다. 하지만 $N$ 이 $4 \times 1 0^{9}$ 에 가깝고, 연속해서 합성수가 많이 나올 경우, 매번 $n$ 까지의 나눗셈을 반복하는 것이 결국 시간 초과를 유발한다는 것을 깨달았다.

실버 4 문제임에도 불구하고 시간 초과가 나는 이유는, 단순히 소수 판정 알고리즘의 효율성 문제뿐 아니라 반복 구조의 효율성까지 고려해야 하기 때문이었다. $4 \times 1 0^{9}$ 범위에서는 $n$ 까지의 모든 소수로 미리 나누어보는 에라토스테네스의 체를 응용하는 것이 정석이라는 것을 알게 되었다.

// 에라토스테네스의 체 응용 (실버 4 정석)
vector<int> primes;
void sieve(){
    int MAX = 63250; // sqrt(4*10^9) 정도의 범위
    vector<bool> isPrime(MAX+1, true);
    // ... (에라토스테네스 체 구현) ...
    for(int i = 2; i <= MAX; i++)
        if(isPrime[i]) primes.push_back(i);
}

bool checkPrime(ll n){ // 미리 뽑아둔 소수들로만 검사
    if(n < 2) return false;
    for(int p : primes){
        if((ll)p*p > n) break; // p*p가 n보다 크면 더 검사할 필요 없음
        if(n % p == 0) return false;
    }
    return true;
}

// main 함수에서
while(!checkPrime(N)) N++;

이해한 내용

이번 학습을 통해 소수 판정법에 대한 이해가 깊어졌고, 다음과 같은 점을 새롭게 알게 되었다.

반례의 존재성을 통한 증명: 소수 판정은 "몇 번 나눗셈을 성공했는가"가 아니라 "나누어떨어지는 수가 존재하는가"라는 존재성 문제로 접근해야 한다는 것을 깨달았다. bool isPrime 변수를 사용하는 것이 이러한 논리 구조를 가장 잘 반영하는 방식임을 알았다.
입력 범위의 중요성: 알고리즘 선택은 문제의 입력 범위를 정확히 파악하는 것에서 시작된다는 것을 절감했다. $1 0^{14}$ 범위에서는 Miller-Rabin 같은 고급 알고리즘이 필요하지만, $4 \times 1 0^{9}$ 범위에서는 sqrt 판정과 에라토스테네스 체 응용으로 충분하다는 것을 배웠다.
코딩 최적화의 미묘함: d*d <= n과 d += 2 같은 사소한 최적화 하나가 시간 초과를 통과하는 결정적인 열쇠가 될 수 있음을 경험했다.

실전 적용

이번 학습 내용을 바탕으로 다음 실습을 계획하고 있다.

알고리즘 문제 풀이: 유사한 "다음 X 찾기" 문제 (예: 다음 완전수, 다음 피자 수 등)에서 비슷한 최적화 전략을 적용해 볼 계획이다.
코딩 테스트 연습: 입력 범위와 문제 유형에 맞는 적절한 알고리즘을 빠르게 선택하는 능력을 기르기 위해 다양한 난이도의 문제를 풀어볼 것이다.
나만의 알고리즘 라이브러리 구축: 에라토스테네스의 체, Miller-Rabin 등 자주 사용되는 알고리즘을 직접 구현하여 재사용 가능한 코드로 만들어두고 싶다.

추가 학습 계획

Miller-Rabin 소수 판정법: $1 0^{14}$ 이상의 큰 수에 대한 소수 판정이 필요할 때 사용할 수 있도록 Miller-Rabin 알고리즘을 깊이 있게 학습하고 구현해 볼 계획이다.
정수론 관련 알고리즘: 소인수분해, 최대공약수, 최소공배수 등 정수론 관련 다양한 알고리즘을 학습하여 문제 해결 능력을 확장하고 싶다.
다양한 자료구조 및 알고리즘 학습: 에라토스테네스의 체와 같이 문제에 따라서는 더 효율적인 자료구조나 알고리즘이 존재함을 알게 되었으므로, 앞으로 다양한 문제 유형에 맞춰 적용할 수 있도록 학습 범위를 넓힐 것이다.

참고 자료

ChatGPT와의 대화 기록: (이 글 자체가 가장 큰 참고 자료)
백준 4134번 문제 페이지: 문제 정의 및 다른 사람들의 풀이 참고
알고리槤 - 에라토스테네스의 체: https://www.algospot.com/learn/course/ch1/sieve (에라토스테네스의 체 이해에 도움)