https://codeforces.com/blog/entry/54090, https://ahgus89.github.io/algorithm/Linear-sieve/

위 의 내용을 참고하여 공부한 내용이다. 1부터 n까지의 각각 수들이 소수인지 판별하는 방법으로 유명한 알고리즘이 에라토스테네스의 체이다. 구현하는 방법은 다음과 같다.

2부터 n까지의 i에 대해서, i가 소수이면 i의 배수들을 합성수로 처리한다. 한 번도 합성수로 처리되지 않았던 수는 소수이다. 그대로 구현하자.

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

이 코드의 시간 복잡도를 생각해 보자. i가 소수일 때 약 n/i번의 내부 반복문을 돌게 된다.

$$ O(∑n/p)=O(nloglogn) $$

임이 이미 알려져 있다. 따라서 에라토스테네스의 체 알고리즘의 시간복잡도는 O(nloglogn)이다.이를 어떻게 최적화할 수 있을까?

비효율이 발생하는 부분은 이미 합성수임이 판별된 수가 다른 소수를 만나 합성수임이 다시 판정될 때이다. 즉, 18은 i가 2일 때, 3일 때 모두 갱신된다. 이 문제를 해결하기 위해 합성수가 합성수임이 한 번만 판별되도록 해야 한다. 모든 합성수는 최소 소인수나머지의 형태로 표현할 수 있음을 이용하면 아래와 같이 구현할 수 있다. “1부터 n까지의 i에 대해서 i가 소수이면 소수 배열에 추가한다. i와 소수 배열의 임의의 j에 대해 ij는 합성수이다. 만약 i가 j의 배수이면 멈춘다.“ j가 최소 소인수이면 합성수 처리를 하고, 아니면 break하므로 선형 시간에 소수 판별 후 소수 배열도 얻을 수 있다. 이를 그대로 구현하자.

for(int i=2;i<=n;i++){
	if(isp[i]) p.push_back(i);
	for(auto j: p)
	{
		if(i*j>n) break;
		isp[i*j]=0;
		if(i%j==0) break;
	}
}

<aside> 💡 정수론에서 소수 판별은 가장 기본이고 중요하므로, 최적화 방법을 알아 두면 후에 많은 도움이 된다. 이에 대한 문제가 있다. https://www.acmicpc.net/problem/16563 정답은 위의 내용을 그대로 구현하면 된다.

</aside>