C++로 소수 가설의 반례 찾기: 반증하는 수를 구하는 알고리즘

숫자 n이 하나 주어져 있다고 가정해 봅시다. 그리고 다음과 같은 가설이 있다고 합니다.

"모든 양의 정수 m에 대하여 (n · m + 1)이 항상 소수가 되는 양의 정수 n이 존재한다."

우리의 목표는 이 명제를 반증할 수 있는 반례(counterexample)가 되는 m을 찾는 것입니다.

문제 예시

입력으로 n = 12가 주어진다면, 출력은 10이 됩니다. 그 이유는 12 × 10 + 1 = 121이 되는데, 121은 11 × 11로 나누어지므로 소수가 아니기 때문입니다.

접근 방법 및 풀이 단계

이 문제는 복잡한 소수 판별 과정 없이 간단한 수학적 성질만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• n ≥ 3인 경우, m = n − 2를 선택하면 n · m + 1 = n(n − 2) + 1 = (n − 1)² 이 됩니다. n − 1이 2 이상이므로 완전제곱수는 절대 소수가 될 수 없습니다.
• n < 3인 경우(즉, n = 1 또는 n = 2), m = n + 2를 선택하면 각각 4와 9가 되어 소수가 아님이 보장됩니다.

따라서 다음 단계를 따르면 됩니다.

if n < 3, then:
    return n + 2
Otherwise
    return n - 2

C++ 구현 예제

위 로직을 C++ 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(int n){
    if (n < 3)
        return n + 2;
    else
        return n - 2;
}
int main(){
    int n = 12;
    cout << solve(n) << endl;
}

실행 결과

입력

12

출력

10

코드 설명

solve 함수는 입력된 n이 3보다 작은지 여부에 따라 반례 m을 결정합니다. n이 3 미만이면 n + 2를, 그렇지 않으면 n − 2를 반환합니다. main 함수에서 n = 12를 전달하면 solve 함수는 12 − 2 = 10을 반환하고, 실제로 12 × 10 + 1 = 121은 소수가 아니므로 가설의 반례임을 확인할 수 있습니다.

이 풀이는 시간 복잡도가 O(1)로 매우 효율적이며, 어떤 양의 정수 n이 입력되더라도 항상 가설에 어긋나는 m을 즉시 찾아낼 수 있습니다.