C++ 소수 판별 알고리즘: 기본 방법부터 페르마의 소정리까지

소수성 테스트란 무엇인가?

이 문제에서는 숫자 N이 주어졌을 때, 해당 숫자가 소수인지 아닌지를 판별하는 것이 목표입니다.

소수성 테스트(Primality Test)는 주어진 숫자가 소수인지 여부를 확인하기 위해 사용되는 알고리즘을 말합니다.

소수(Prime Number)란 1과 자기 자신으로만 나누어 떨어지는 수를 의미합니다. 예를 들어 2, 3, 5, 7 등이 있습니다.

간단한 예시를 통해 문제를 살펴보겠습니다.

입력: 11
출력: Yes

방법 1: 나눗셈을 이용한 기본 접근

숫자의 소수 여부를 확인하는 방법은 여러 가지가 있습니다.

가장 단순한 방법은 N보다 작은 모든 숫자로 나누어 보는 것입니다. 만약 어떤 숫자든 N을 나눌 수 있다면, N은 소수가 아닙니다.

즉, i = 2부터 n-1까지 모두 검사했을 때 n % i == 0인 경우가 하나라도 존재하면 그 수는 소수가 아닙니다.

이 방법은 알고리즘에 몇 가지 개선 사항을 적용하면 훨씬 더 효율적으로 만들 수 있습니다.

개선점 1: √n까지만 검사하기

첫 번째 개선점은 n 대신 √n까지의 값만 검사하는 것입니다. 이렇게 하면 반복문의 실행 횟수를 크게 줄일 수 있습니다. √n까지의 범위에는 n의 모든 가능한 약수가 포함되기 때문입니다.

개선점 2: 2와 3을 먼저 처리한 뒤 6씩 증가시키기

두 번째 개선점은 2와 3으로 나누어 떨어지는 경우를 먼저 확인하고, 이후에는 5부터 √n까지 반복문을 돌며 6씩 증가시키면서 검사하는 것입니다. 이는 모든 소수가 6k±1 형태라는 수학적 성질을 활용한 최적화 기법입니다.

알고리즘 구현 예제

#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
    if (n <= 1)
        return false;
    if (n <= 3)
    return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0)
    return false;
    return true;
}
int main() {
    int n = 341;
    if (isPrimeNumber(n))
        cout<<n<<" is prime Number.";
    else
        cout<<n<<" is not prime Number.";
    return 0;
}

실행 결과

341 is not prime Number.

방법 2: 페르마의 방법(Fermat's Method)

보다 효과적인 소수 판별 방법으로는 페르마의 방법이 있으며, 이는 페르마의 소정리(Fermat's Little Theorem)에 기반합니다.

페르마의 소정리: N이 소수라면, (1, n-1) 범위에 속하는 모든 값 a에 대해 다음 식이 성립합니다.

an-1 ≡ 1 (mod n)
또는
an-1 % n = 1

이 정리를 활용한 구현 프로그램은 다음과 같습니다.

#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
    int res = 1;
    a = a % p;
    while (n > 0){
        if (n & 1)
        res = (res*a) % p;
        n = n/2;
        a = (a*a) % p;
    }
    return res;
}
int gcd(int a, int b) {
    if(a < b)
        return gcd(b, a);
    else if(a%b == 0)
        return b;
    else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    while (k>0){
        int a = 2 + rand()%(n-4);
        if (gcd(n, a) != 1)
            return false;
        if (power(a, n-1, n) != 1)
            return false;
        k--;
    }
    return true;
}
int main() {
    int k = 3, n = 23;
    if(isPrime(n, k)){
        cout<<n<<" is a prime number";
    }
    else
        cout<<n<<" is not a prime number";
    return 0;
}

실행 결과

23 is a prime number