윌슨의 정리로 n보다 작은 모든 소수 구하기 – 흥미로운 알고리즘 소개

이 글에서는 n보다 작은 모든 소수를 효율적으로 구하는 흥미로운 방법을 살펴봅니다. 핵심 아이디어는 윌슨의 정리(Wilson's theorem)입니다. 윌슨의 정리에 따르면, 어떤 수 k가 소수일 때 ((k - 1)! + 1) mod k의 값은 반드시 0이 됩니다. 즉, 이 성질을 역으로 이용하면 특정 수가 소수인지 판별할 수 있습니다.

다만 이 방법에는 중요한 제약이 있습니다. C나 C++처럼 고정 크기 정수형을 사용하는 언어에서는 그대로 적용하기 어렵습니다. 팩토리얼은 기하급수적으로 커지기 때문에, 예를 들어 13!만 되어도 32비트 int의 최대 표현 범위(약 21억)를 이미 초과합니다. 따라서 실제 실행 시 오버플로우로 인해 올바른 결과를 보장할 수 없으며, 개념 이해를 위한 학습용 예제로 보는 것이 좋습니다.

알고리즘

genAllPrime(n)

시작
    fact := 1
    i를 2부터 n-1까지 반복:
        fact := fact * (i - 1)
        만약 (fact + 1) mod i = 0이면
            i 출력
    반복 끝
종료

여기서 눈여겨볼 점은 매번 (i-1)!을 새로 계산하지 않고, 이전 단계의 fact 값에 (i-1)을 곱해 누적한다는 것입니다. 덕분에 각 단계마다 팩토리얼을 처음부터 다시 구하는 불필요한 연산 비용을 줄일 수 있습니다.

C++ 예제 코드

#include <iostream>
using namespace std;

void genAllPrimes(int n){
    int fact = 1;
    for(int i = 2; i < n; i++){
        fact = fact * (i - 1);
        if((fact + 1) % i == 0){
            cout << i << " ";
        }
    }
}

int main() {
    int n = 10;
    genAllPrimes(n);
}

실행 결과

2 3 5 7

n이 10일 때, 10보다 작은 소수인 2, 3, 5, 7이 정상적으로 출력됩니다.

마무리 및 참고 사항

윌슨의 정리는 소수 판별의 아름다운 이론적 성질을 보여주지만, 팩토리얼 연산의 폭발적인 증가와 오버플로우 문제 때문에 실전에서는 거의 사용되지 않습니다. 실제 프로그래밍에서 n 이하의 소수를 구하려면 에라토스테네스의 체(Sieve of Eratosthenes) 같은 방법이 훨씬 효율적이며 널리 활용됩니다. 반면 Python의 int처럼 임의 정밀도 정수를 기본 지원하는 언어에서는 이 방식을 개념 검증 용도로 실험해볼 수도 있습니다.