에라토스테네스의 체 편집하기

'''에라토스테네스의 체'''(sieve of Eratosthenes)는 특정 범위의 [[자연수]] 중 [[소수 (정수)|소수]]를 찾는 알고리즘이다. 명칭에서 알 수 있듯이 고대 그리스의 수학자인 에라토스테네스가 처음 고안한 방법으로, 꽤 고전적인 방법이면서도 소수 찾기의 초석이 되는 데 의미가 있다.

== 아이디어 ==
2부터 <math>N</math>까지의 자연수 집합이 주어져 있다. 목표는 이 집합 내에서 [[합성수]]를 걸러내고 소수들만 남기는 것이다. 에라토스테네스의 체의 알고리즘을 세우는 데 앞서 아래 정리들을 짚고 넘어간다.

* 모든 자연수 <math>1<m<\sqrt{n}</math>에 대해 <math>m \nmid n</math>이면 <math>n</math>은 소수이다.
* 자연수 <math>a,b,n</math>에 대해 <math>ab \mid n</math>이면 <math>a \mid n, b \mid n</math>이다. 즉 <math>a \nmid n</math>이라는 사실이 확인되면 자동으로 모든 <math>a</math>의 배수는 <math>n</math>의 약수가 아니게 된다.
* 1을 제외한 가장 작은 약수가 <math>q</math>인 합성수 중 가장 작은 수는 <math>q^2</math>이다.

첫째와 둘째 정리를 종합하면, <math>\sqrt{N}</math> 이하의 모든 소수들로 나눗셈을 해보면 <math>N</math> 이하의 모든 합성수를 지울 수 있다.

== 알고리즘 ==
[[파일:Sieve of Eratosthenes animation.gif|오른쪽]]
오른쪽 그림은 2부터 120까지의 자연수에 대한 에라토스테네스의 체의 적용 과정을 나타낸 것으로, 아래 방법을 따라간다.

*<math>p \le \lfloor \sqrt{120} \rfloor</math>을 만족하는 소수 <math>p</math>를 먼저 찾는다. 이 소수들은 2, 3, 5, 7이다.
*2를 제외한 2의 배수를 지운다. (4부터 시작)
*3을 제외한 3의 배수를 지운다. (9부터 시작)
*5를 제외한 5의 배수를 지운다. (25부터 시작)
*7을 제외한 7의 배수를 지운다. (49부터 시작)
*다음 소수는 11이지만 11의 제곱은 121로 주어진 범위를 벗어난다. 따라서 여기까지 남은 수들은 모두 소수이다.

== 집합을 이용한 접근 ==
위 글을 집합을 도입해서 서술하면 아래와 같이 써진다.

먼저 몇 가지 문자를 정의한다.
*<math>P_1 = \emptyset</math>
*<math>A_1 = \{x \in \mathbb{N}|2 \le x \le N \}</math>
*<math>p_k</math>는 집합 <math>A_k</math> 내의 가장 작은 원소이다. 즉 <math>p_k=\min(A_k)</math>이며, 이는 <math>k</math>번째 소수를 의미한다.
*<math>B_k = \{p_k x| x \in A_k,p_k x \le N \}</math>
*<math>A_{k+1} = A_{k} \setminus (B_k \cup \{p_k \})</math>
*<math>P_{k+1} = P_{k} \cup \{p_k \}</math>
*<math>B_m = \emptyset</math>이 되면 알고리즘을 종료한다. 이때 <math>P_m \cup A_m</math>이 바로 <math>N</math> 이하의 소수들의 집합이다.

가령 <math>N=120</math>일 때, 알고리즘은 아래와 같이 서술할 수 있다.

#<math>P_1 = \emptyset,\ A_1 = \{2, 3, 4, 5, \cdots 119, 120 \}</math>
#*<math>p_1 = \min(A_1) = 2</math>: 첫 번째 소수는 2이다.
#*<math>B_1 = \{4, 6, 8, 10, \cdots 118, 120 \}</math>: 이 집합은 1을 제외한 가장 작은 약수가 2인 120 이하의 합성수들을 모은 것이다.
#*<math>A_1</math>에서 <math>B_1</math>의 원소들을 지운다. 또, 나눗셈 검사를 마친 원소인 2는 <math>A_1</math>에서 빼고 <math>P_2</math>에 넣는다.
#<math>P_2 = \{2 \},\ A_2 = A_1 \setminus (B_1 \cup \{2 \}) = \{3, 5, 7, 9, \cdots 117, 119 \}</math>
#*<math>p_2 = \min(A_2) = 3</math>: 두 번째 소수는 3이다.
#*<math>B_2 = \{9, 15, 21, 27, \cdots 111, 117 \}</math>: 이 집합은 1보다 큰 가장 작은 약수가 3인 합성수들을 모은 것이다.
#*같은 방법으로 <math>B_2</math>의 원소들을 제외하고, 3은 <math>P_3</math>에 넣는다.
#<math>P_3 = \{2, 3 \},\ A_3 = A_2 \setminus (B_2 \cup \{3 \}) = \{5, 7, 11, 13, \cdots 115, 119 \}</math>. 이어서 똑같은 방법을 반복한다.
#*<math>p_3 = 5</math>: 세 번째 소수는 5이다.
#*<math>B_3 = \{25, 35, 55, 65, 85, 95, 115 \}</math>
#<math>P_4 = \{2, 3, 5 \},\ A_4 = \{7, 11, 13, 17, \cdots 113, 119 \}</math>
#*<math>p_4 = 7</math>: 네 번째 소수는 7이다.
#*<math>B_4 = \{49, 77, 91, 119 \}</math>
#<math>P_5 = \{2, 3, 5, 7 \},\ A_5 = \{11, 13, 17, 19, \cdots 109, 113 \}</math>
#*<math>p_5=11,\ p_5^2 = 121 > N</math>이므로 <math>B_5 = \emptyset</math>이다. 이로써 알고리즘은 여기서 끝난다.
#<math>P_5 \cup A_5 = \{2, 3, 5, 7, 11, 13, 17, 19, \cdots 109, 113 \}</math>으로, 이것이 우리가 찾고자 한 120 이하의 소수들의 집합이다. 참고로 <math>P_5</math>는 <math>\sqrt{N}</math> 이하의 소수들의 집합, <math>A_5</math>는 <math>\sqrt{N} < p \le N</math> 범위의 소수들을 모은 집합이다.

{{각주}}
{{수론 알고리즘}}
[[분류:정수론]]