알고리즘 문제해결 전략

Ch.14.2 소수

종만북

14.2 소수

소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미합니다.
소수의 반대말로, 세 개 이상의 양의 약수를 갖는 자연수를 합성수(composite number)라고 부릅니다.

소수 판별

주어진 수 n이 소수인지를 판단하는 가장 단순한 방법은 2부터 n-1까지의 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인하는 것입니다.

약수가 하나도 없다면 n이 소수란 사실을 알 수 있습니다.

거기에 합성수 n이 pxq로 표현될 때 한 수는 항상 root(n)이하, 다른 한 수는 항상 root(n)이상이라는 점을 이용하면 n-1까지 순회하지 않고 root(n)까지만 순회하도록 최적화 할 수 있습니다.

// 주어진 자연수 n이 소수인지 확인한다.
bool isPrime(int n){
    // 예외 처리: 1과 2는 예외로 처리한다.
    if(n <= 1)return false;
    if(n == 2)return true;
    if(n % 2 == 0)return false;
    int sqrtn = sqrt(n);
    for(int div = 3; div <= sqrtn; div += 2)
        if(n % div == 0)
            return false;
    return true;
}

소인수 분해

소인수 분해를 하는 가장 쉬운 방법은 앞에서 다룬 간단한 소수 판별 알고리즘을 응용하는 것입니다.

2부터 시작해 n의 소인수가 될 수 있는 수들을 하나하나 순회하면서, n의 약수를 찾을 때마다 n을 이 숫자로 나눕니다.

이 알고리즘은 n이 소수인 경우 root(n)번 반복문을 돌기 때문에 시간 복잡도는 O(root(n))이 됩니다.

// 주어진 정수 n을 소인수분해하는 간단한 알고리즘
vector<int> factorSimple(int n){
    vector<int> ret;
    int sqrtn = sqrt(n);
    for(int div = 2; div <= sqrtn; div++)
        while(n % div == 0){
            n /= div;
            ret.push_back(div);
        }
    return ret;
}

에라토스테네스의 체

에라토스테네스의 체(Sieve of Eratoschenes)는 주어진 수 n이하의 소수들을 모두 찾아냅니다.

에라토스테네스의 체는 사실상 앞에서 다룬 간단한 소수 판별 알고리즘을 [2,n]범위의 모든 자연수에 대해 확장한 것입니다.

단 각 수 m이 소수인지 판단하기 위해 root(m)까지의 모든 수로 나눠보는 대신, 소수를 찾을 때마다 그 배수들을 지우는 형태로 동작하기 때문에 훨씬 빠르게 수행됩니다.

두 가지 최적화 방법

지워지지 않은 수를 찾을 때 n이 아니라 root(n)까지만 찾습니다. 이것은 소수 판정 알고리즘에서 이용한 것과 똑같은 최적화입니다.

더 흥미로운 최적화 방식은 i의 배수들을 모두 지울 때 2xi에서 시작하는 것이 아니라 ixi에서 시작하는 것입니다. 2xi는 이미 2의 배수를 지울 때 지워졌을 테고, 3xi는 3의 배수를 지울때 이미 지워졌을 테니까요.

시간복잡도 : 실용적인 범위 내에서 O(n)과 비슷

int n;
bool isPrime[MAX_N+1];
// 가장 단순한 형태의 에라토스테네스의 체의 구현
// 종료한뒤 isPrime[i] = i가 소수인가?
void eratosthenes(){
    memset(isPrime, 1, sizeof(isPrime));
    // 1은 항상 예외처리!
    isPrime[0] = isPrime[1] = -1;
    int sqrtn = sqrt(n);
    for(int i = 2; i <= sqrtn; i++){
        // 이 수가 아직 지워지지 않았다면
        if(isPrime[i])
            for(int j = i*i; j <= n; j += i)
                isPrime[j] = false;
    }
}

예제: 에라토스테네스의 체를 이용한 빠른 소인수 분해

만약 정해진 범위의 수들에 대해 소인수 분해를 여러 번 해야 한다면 에라토스테네스의 체를 응용해 훨씬 빠르게 소인수 분해를 수행할 수 있습니다.

최적화의 비결은 체에서 각 숫자가 소수인지 합성수인지만을 기록하는 것이 아니라, 각 숫자의 가장 작은 소인수를 같이 기록해 두는 것입니다.

예를 들어 28 = 2 x 2 x 7 의 가장 작은 소인수 2를 기록하는 것입니다.

// minFactor[i] = i의 가장 작은 소인수 (i가 소수인 경우 자기 자신)
int minFactor[MAX_N];
// 에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보도 저장한다.
void eratosthenes2(){
    // 1은 항상 예외처리
    minFactor[0] = minFactor[1] = -1;
    // 모든 숫자를 처음에는 소수로 표시해둔다.
    for(int i = 2; i <= n; i++)
        minFactor[i] = i;
    // 에라토스테네스의 체를 수행한다.
    int sqrtn = sqrt(n);
    for(int i = 2; i <= sqrtn; i++)
        if(minFactor[i] == i)
            for(int j = i*i; j <= n; j += i)
                // 아직 약수를 본 적 없는 숫자인 경우 i를 써 둔다.
                if(minFactor[j] == j)
                    minFactor[j] = i;

}
// 2 이상의 자연수 n을 소인수분해한 결과를 반환한다.
vector<int> factor(int n){
    vector<int> ret;
    // n이 1이 될 때까지 가장 작은 소인수로 나누기를 반복한다.
    while(n > 1){
        ret.push_back(minFactor[n]);
        n /= minFactor[n];
    }
    return ret;
}