내가 보려고 만든 소인수분해 방법 정리글

https://booknu.github.io/2019/01/17/오일러의 체

오일러의 체 - 빠른 소인수분해, 소수 찾기

이게 정말 효율적인 소수 판별법인데 주기적으로 복습하지 않으면 그 논리를 계속 까먹는다.

 

<본문의 핵심 코드> 출처는 위 링크

코드 설명 

spf[x] : x의 가장 작은 소인수 spf[x]==x 이면 x는 소수

pn: 지금까지 찾은 소수의 개수

pr[x] : x-1번째 소수 

 

#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i)) 
const int RANGE = 1e7; 
int pn, spf[RANGE], pr[RANGE]; 
void eulerSieve() { 
    FOR(x, 2, RANGE) { 
        if(!spf[x]) spf[x] = pr[pn++] = x; 
        // 현재 x에 대해 spf가 정해지지 않았다는 것은 spf[x] = x라는 의미이고, x가 소수라는 의미이다.
           for(int j = 0; x*pr[j] < RANGE; ++j) { 
            spf[x*pr[j]] = pr[j]; // 수 * spf들에 대해 spf[x*spf] = spf로 칠해준다. 
            if(x % pr[j] == 0) break; // spf[x] == pr[j]이면 그만 둔다. (이 이상 pr이 늘어나면 x * pr에 대해 더 이상 spf가 pr이 아닌 x의 spf이니까) 
            } 
        } 
    }
 
 

핵심 논지는 소수의 배수로 체를 칠하던 것을

각 소수를 spf(smallest prime factor)로 가지는 합성수로 체를 칠하다는데 있다.

 

그렇다면 spf(x)>=pr[j] 인 것을 어떻게 판단하느냐? 

pr[j]는 어차피 지금까지 판단한 소수들 2,3,5.. 부터 차례대로 살펴보므로

pr[j]가 x를 나누는 순간 Loop를 끊어버리면 그전까지 spf(x) >= pr[j]임을 확신할 수 있다.

 

spf 를 이용하면 소인수 분해를 빠르게할 수 있다.

 

while(x!=1){
    printf("%d ",spf[x]);
    x/=spf[x];
}