[알고리즘] 소수 구하기 - 에라토스테네스의 체

"에라토스테네스의 체" 는 수학에서 소수를 찾는 방법이다.

 

문장으로 설명하는 방법은 아래와 같다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

이와 같은 방법을 c++ 언어로 직접 구현한 소스코드는 아래와 같다.

 

#include <iostream>

using namespace std;

/* 에라토스테네스의 체 - 소수찾기 알고리즘 */
/* 숫자의 범위가 1 ~ 1000 이라고 가정 */

int main()
{
	int n = 1000;
	bool check[1001];

	memset(check, true, sizeof(check)); // 배열 true로 전부 채우기

	check[0] = check[1] = false; // 0과 1은 소수가 아니므로 false

	for(int i = 2; i < sqrt(n); i++)
	{
		if(check[i])
		{
			for (int j = i + i; j <= n; j += i)
				check[j] = false;
		}
	}

	for(int i = 0; i <= n; i++)
	{
		if (check[i])
			cout << i << endl;
	}
}

 

먼저, 구하고자 하는 소수의 범위를 n 변수에 저장한 뒤, 그보다 1 증가한 bool 배열을 초기화한다.

(bool 배열의 크기를 n+1 하여, 숫자와 배열의 인덱스를 동일하게 사용하기 위함)

 

이후, bool 배열 전체를 true로 초기화한 뒤, 소수 검사를 거치며 소수가 아닌 경우 false로 변경하였다.

 

숫자 0과 1은 소수가 아니므로 바로 false로 초기화해주었고, 이후에는 int i = 2 부터 n의 제곱근까지 반복문을 수행하며 bool 변수가 true라면 그 이후의 배수들을 false로 변경하는 과정을 진행하였다.

 

🚩 i = 2

j = 2+2 =4, 4 <= 1000, 
check[4] = false;

j+= 2  -> j = 6
check[6] = false;

j+=2  -> j = 8
check[8] = false;
.
.
.
j+=2  -> j = 1000
check[1000] = false;

 

🚩 i = 3

j = 3+3 =6, 6 <= 1000, 
check[6] = false;

j+= 3  -> j = 9
check[9] = false;
.
.
.
j+= 3  -> j = 999
check[999] = false;

 

이때의 포인트는 bool 변수를 false로 체크할 때, i 번째는 false로 체크하지 않고, true인채로 넘어가는 것이다!

배수만 false로 체크하여 "자기자신과 1외에 아무런 약수가 없는 수"인 소수를 찾아낼 수 있다.

 

시간복잡도

O(nlog(logn))

---

참조

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전