[소수 알고리즘] 소수의 특성과 에라토스테네스의 체

[소수 알고리즘] 소수의 특성과 에라토스테네스의 체

소수의 특성

소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수이다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현된다.

예를 들면,

$$ 91 = 7 * 13 $$

$$ 10164 = 7 * 11^2 * 12 $$

이를 소인수 분해의 일의성이라고 하는데 이 특징은 최대 공약수를 구하는데 매우 유용하게 사용될 수 있다. 최대 공약수는 두 개 이상의 자연수가 가지는 약수 중 가장 큰 수이다. 약수 또한 자연수 이므로 하나의 소수들의 곱으로 표현된다. 즉 최대 공약수를 구하려는 수들의 공통된 소수들을 모두 곱해 주면 최대 공약수가 되는 것이다.

$$ 300 = 2^2 * 3^1 * 5^2, 18 = 2^1 * 3^2 $$

$$ GCD(300, 18) = 2^1 * 3^1 = 6 $$

소수는 더 이상 쪼갤 수 없는 수이기 떄문에, 어떤 수의 특징을 나타내는데 매우 적합한 수이다.

소수 구하는 알고리즘

소수를 구하는 방법은 아주 많이 있는데 기본적인 방법부터 지구 둘레의 길이를 처음으로 계산한 에라토스테네스라는 그리스의 수학자의 방법까지 살펴 보도록 하자. 소수 구하려는 수를 N이라고 하겠다.

- 기본적인 접근

소수는 1과 N 만을 약수로 가진다. 그럼 2부터 N-1까지의 수로는 나눠져서는 안된다.

#include <iostream>
using namespace std;
 
int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;
    bool isPrime = true;
 
    // 2부터 N-1의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
    for (int i=2; i<num; ++i)
    {
        if (num / i == 0)
        {
            isPrime = false;
            break;
        }
    }
 
    if(isPrime)
        cout << num << "은 소수입니다." << endl;
    else
        cout << num << "은 소수가 아닙니다." << endl;
 
    return 0;
}
 
 

연산 횟수 : N-2번

- 에라토스테네스의 접근

주어진 자연수 N이 소수이기 위한 필요 충분조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 $\sqrt{N}$ 이하이기 때문이다.

즉, 2부터 $\sqrt{N}$까지 나눠보면 된다.

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;
    bool isPrime = true;
 
    // 2부터 N-1의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
    for (int i=2; i<=sqrt(num); ++i)
    {
        if (num / i == 0)
        {
            isPrime = false;
            break;
        }
    }
 
    if(isPrime)
        cout << num << "은 소수입니다." << endl;
    else
        cout << num << "은 소수가 아닙니다." << endl;
 
    return 0;
}
 
 

연산 횟수 : $\sqrt{n-2}$번

- 에라토스테네스의 체

에라토스테네스의 체는 매우 간단한 아이디어이다. 위에서 모든 자연수는 소수들의 곱으로 표현이 된다고 했다. 제일 작은 소수 2부터 시작한다. 2부터 N-1까지의 수 중에서 2의 배수를 모두 체로 거르고 남은 숫자들 중에서 3의 배수로 거르고를 반복해서 $\sqrt{n}$까지 나눠서 남은 걸러지지 않고 남은 수들이 모두 소수가 된다. 이해를 돕기 위해 아래 애니메이션을 첨부 하였다.

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    unsigned int num;
    cout << "소수를 구할 수를 입력하세요 : ";
    cin >> num;
    bool isPrime = true;
 
    bool* bArr;
    bArr = new bool[num+1];
    
    for (int i=2; i<=num; ++i)
        bArr[i] = true;
 
    for (int i=2; i<=sqrt(num); ++i)
    {
        if (bArr[i])
        {
            for (int j=i*i; j<=num; j+=1)
                bArr[j] = false;
        }
 
    }
 
    for (int i=2; i<num; ++i)
    {
        if (bArr[i] == true)
        {
            isPrime = true;
            break;
        }
    }
 
    if(isPrime)
        cout << num << "은 소수입니다." << endl;
    else
        cout << num << "은 소수가 아닙니다." << endl;
 
    return 0;
}

실행 시간이 증가한 것을 볼 수 있는데 이는 에라토스테네스의 체는 2부터 N-1까지 소수 여부를 저장할 수 있는 공간이 필요하기 때문이다. 

주어진 수가 소수인지 아닌지 판별만 할 경우는 2번째 방법을 사용하는 것이 좋다.

주어진 수 까지의 모든 소수를 구하기 위해서는 에라토스테네스의 체를 사용한다.

정리

소수를 판정하는 알고리즘은 매우 많다. 에라토스테네스의 방법은 매우 고전적인 방법이지만 소수의 특성을 이해하기에 좋은 알고리즘이다.

소수 판정 알고리즘은 결정적 소수판정 알고리즘과 확률적 소수판정 알고리즘으로 나누어 진다. 결정적 소수판정 알고리즘(Deterministic Algorithm)은 소수인지 아닌지 정확하게 판별하는 알고리즘이다. 에라토스테네스 방법, 유클리드 호제법, 페르마 방법, 윌슨 방법, APR 방법 등이 있다. 확률적 소수판정 알고리즘(Probabilistic Algorithm)은 주어진 수가 소수일 확률을 구하는 알고리즘이다. 틀릴 확률이 존재하지만 빠르게 높은 확률의 답을 얻을 수 있다. Solovay-Strassen 알고리즘, Lehmann-Peralta 알고리즘, Miller-Rabin 알고리즘이 있다.

또한 메르센 소수, 페르마 소수 등 특수한 소수들이 존재하고 아직도 더 큰 소수를 구하기 위한 연구들이 계속해서 진행되고 있다.