[C++ 에라토스테네스의 체] 소수 판별법

0. 배경 지식

---

소수는 1과 자신만을 약수로 갖는 수.

앞서 설명한 약수의 개념이 사용되므로 1부터 N까지 수들 중 소수로 판별해야 한다면

기존의 시간 복잡도에 N을 곱해서 O(N^2) 혹은 O(N √N) 이다.

 

더 좋은 방법은 소수가 아닌 수들을 걸러내는 것이다.

이 방법이 "에레토스테네스의 체" 이다.

 

체로 소수가 아닌 수들을 걸러내는 것

1. 동작 순서

---

https://ko.wikipedia.org/wiki/%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

위의 링크의 설명 GIF 이미지를 가져왔다.

 

1) 2부터 N까지 모든 정수를 적는다.

2) 아직 지우지 않은 수들 중 가장 작은 소수를 찾는다. 이를 P라 한다.

3) 아직 지우지 않은 수들 중 P의 배수를 크기 순으로 지운다.

4) 아직 모든 수를 지우지 않았다면 다시 2번 단계로 간다.

 

=> O(N log(log N)) 의 시간 복잡도!

 

2. 실제 구현법

---

for(int i=2; i<= N; ++i){
	// 아직 지우지 않은 수 중 가장 작은 소수를 찾음.
	// bool 자료형 배열 is_prime 안에 모든 요소들에 대해 처음에 True로 초기화.
	// 1은 소수가 아니니 i는 2부터 시작.
	// j는 i만큼 계속 커지도록 해서, i를 제외한 N이하의 모든 i의 배수를 빠르게 체크.
	
	if(is_prime[i])
	{
		for(int j = i * 2 ; j <= N ; j+= i)
		{
			// j가 소수가 아님을 is_prime 배열에 체크.
			if(is_prime[j]) is_prime[j] = false;
		}
	}
}

// 이후 is_prime[i] = true인 모든 i는 소수가 됨.