인수분해 (에라토스테네스의 체)

에라토스테스의 체는 소수를 찾는데 사용되지만, 

약간의 변형을 통해, 합성수를 소인수분해 하는데 사용할 수 있다.

 

에라토스테네스의 체(Sieve of Eratosthenes)에 대한 내용은 여기로

소수 찾기 C++ 코드는 여기로

---

합성수 N의 소인수 중 하나가 P이면,

N의 모든 소인수는 P와 $\frac{N}{P}$의 분해로 이루어져 있다.

 

에라토스테네스의 체를 활용하면 최소 소인수를 기록해 두고, 활용할 수 있다.

 

예시)

 

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	0	0	2	0	2	0	2	3	2	0	2	0	2	3	2	0	2	0	2

 

1행은 숫자(N)을 의미한다.

2행은 숫자(N)의 최소 소인수를 의미한다.

 

합성수 4의 최소 소인수는 2이다.

합성수 6의 최소 소인수는 2이다.

합성수 8의 최소 소인수는 2이다.

합성수 9의 최소 소인수는 3이다.

...

 

기존의 에라토스테네스의 체는 소수인지, 합성수인지 구분하는데 사용했다면,

이번에는 합성수의 최소 소인수를 기록해서, 인수분해에 활용하고 있다.

 

코드 (C++)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    //최소 소인수 찾기(에라토스테네스의 체 변형)
    const int N = 60;
    vector<int> A(N + 1, 0);
    for (int i = 2; (i * i) < (N + 1); i++) //sqrt(N)까지만 진행
    {
        //A[i] != 0 이면, 이미 A[i]에 대한 최소 소인수를 찾은 상태이다
        if (A[i] == 0)
        {
            int k = i * i;
            while (k < (N + 1))
            {
                if(A[k] == 0) A[k] = i;
                k += i;
            }
        }
    }

    //합성수(N)의 소인수분해
    vector<int> factors = {};
    int P = N; //x = 60
    while (A[P] > 0) //A[P] > 이면, P는 합성수
    {
        factors.emplace_back(A[P]); //P의 최소 소인수는 A[P]
        P /= A[P]; //P는 최소 소인수 A[P]로 나누어 떨어진다
    }
    factors.emplace_back(P);

    return 0;
}