에라토스테네스의 체로 소인수분해 하기

이번 글에서는 에라토스테네스의 체를 이용해 소인수분해를 빠르게 하는

방법을 다루고자 한다.

 

https://www.acmicpc.net/problem/3142

 

이 문제를 풀던 도중 이 방법을 알게 되었다.

기본적인 에라토스테네스의 체 구현보다 최적화된 구현과 함께 알게 되었다.

https://velog.io/@pakuland3/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-%EC%B5%9C%EC%A0%81%ED%99%94optimized-sieve-of-eratosthenes

에라토스테네스의 체 최적화(optimized sieve of eratosthenes)

 

기본적인 에라토스테네스의 체 구현 형태는 다음과 같다.

 

for(int i=2;i<=n;i++){
	if(sieve[i]) continue;
	for(int j=2*i;j<=n;j+=i) sieve[j]=1;
}

 

이때 $j$ 의 시작을 $i^2$ 부터 하고, $sieve[j]$ 에 소수 여부만을 담는 것이 아닌 $j$의 가장 작은 소인수를 담는다.

 

구현은 다음과 같다.

 

for(int i=2;i<=n;i++){
	if(sieve[i]) continue;
    sieve[i]=i;
	for(int j=i*i;j<=n;j+=i) sieve[j]=i;
}