48. Prime Factorization

소인수분해(Prime Factorization)는 양의 정수를 소수들의 곱으로 나타내는 것으로 다양한 문제에서 등장하는 개념이다. 소인수분해를 하는 방법은 다양하고 응용 범위도 넓은 편이기 때문에 각각의 상황에 맞는 소인수분해 방법을 선택하는 것이 좋다.

 

가장 간단한 소인수분해 방법은 다음과 같다.

vector<int>v;
void f(int n)
{
    for(int i = 2; i <= n; i++)
    {
        while(n % i == 0)
        {
            v.push_back(i);
            n /= i;
        }
    }
}

$2$ 이상 $n$ 이하의 모든 정수를 확인하면서 $n$이 $i$의 배수이면 $i$를 소인수 목록에 추가하고 $n$을 $i$로 나눈 다음 계속 진행한다. 하지만 이 방법은 $n$이 $1$억 정도의 소수일 경우 성능이 상당히 떨어진다. 다행히도 위의 코드를 조금만 수정하면 성능은 매우 좋아진다.

vector<int>v;
void f(int n)
{
    for(int i = 2; i * i <= n; i++)
    {
        while(n % i == 0)
        {
            v.push_back(i);
            n /= i;
        }
    }
    if(n > 1)v.push_back(n);
}

두 코드에서 $f$ 함수를 실행한 결과는 같지만, 성능은 두 번째 코드가 더 좋다. 두 번째 코드는 $n$이 $1$억 정도여도 바깥쪽 반복문은 최대 $1$만 번만 실행되므로 빠르게 소인수분해를 할 수 있다.

짝수 소수가 $2$밖에 없다는 점을 이용하면 조금 더 효율적인 코드를 작성할 수도 있다.

vector<int>v;
void f(int n)
{
    while(n % 2 == 0)
    {
        v.push_back(2);
        n /= 2;
    }
    for(int i = 3; i * i <= n; i += 2)
    {
        while(n % i == 0)
        {
            v.push_back(i);
            n /= i;
        }
    }
    if(n > 1)v.push_back(n);
}

세 번째 코드에서는 $i$가 $2$씩 증가하므로 실행 속도가 두 번째 코드보다 $2$배 정도 빠르다. 다만 대부분의 문제의 경우 세 번째 코드로 풀 수 있다면 두 번째 코드로도 풀 수 있으므로 효율성에 비해 많이 쓰이지는 않는 편이다.

 

여기서 설명한 소인수분해 방법은 $n$이 $10^{15}$ 이하라면 나름 괜찮은 성능을 보이지만 $n$이 그 이상으로 커지면 성능이 급격하게 떨어진다. 또한 $n$의 범위가 작지만 소인수분해를 해야 할 수가 여러 개인 경우 이 방법으로 각각의 수들을 소인수분해하는 것은 비효율적이라는 문제점도 존재한다. 이 두 가지 문제점을 해결하는 방법이 각각 존재한다. 여러 개의 수를 소인수분해할 때는 에라토스테네스의 체를 이용할 수 있다. 수의 범위가 큰 경우에는 폴라드 로를 이용하면 된다. 폴라드 로에 대한 글은 추후 작성할 예정이다.

 

[연습문제]

 

BOJ 11653. 소인수분해 (Silver IV)

앞에서 설명한 대로 소인수분해를 하면 된다.

 

→ solved.ac tag: primality_test