에라토스테네스의 체

1. 개요

---

Sieve of Eratosthenes
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 따지고 보면 $$f \left(x\right) = \dfrac{x}{\bold{1}_{\mathbb{P}}(x)}$$[1]의 수열을 표로 시각화한 것이라고 볼 수 있다.

2. 방법

---

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 '''간단하고 빠른'''[2] 방법이다. 예를 들어 1~100까지 숫자 중 소수를 찾는다 하자.

일단 1부터 100까지 숫자를 쭉 쓴다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

일단 1을 지우자.(1은 소수도, 합성수도 아니며, 기초수라고 해서 별도로 분류한다.)

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

2를 제외한 2의 배수를 지우자.

	'''2'''	3		5		7		9
11		13		15		17		19
21		23		25		27		29
31		33		35		37		39
41		43		45		47		49
51		53		55		57		59
61		63		65		67		69
71		73		75		77		79
81		83		85		87		89
91		93		95		97		99

3을 제외한 3의 배수를 지우자.

	2	'''3'''		5		7
11		13				17		19
		23		25				29
31				35		37
41		43				47		49
		53		55				59
61				65		67
71		73				77		79
		83		85				89
91				95		97

4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.[A]

)
그러면 2, 3 다음으로 남아있는 가장 작은 소수, 즉 5의 배수를 5를 제외하고 지우자.

	2	3		'''5'''		7
11		13				17		19
		23						29
31						37
41		43				47		49
		53						59
61						67
71		73				77		79
		83						89
91						97

그리고 마지막으로 7을 제외한 7의 배수까지 지우면 결과는 이렇다.(여기까지만 지우는 이유는 후술한다.)

	2	3		5		'''7'''
11		13				17		19
		23						29
31						37
41		43				47
		53						59
61						67
71		73						79
		83						89
						97

8의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.[A]) 9의 배수도 지울 필요 없다.(3의 배수에서 이미 지워졌다.[A]) 10의 배수도 지울 필요 없다.(2의 배수에서 이미 지워졌다.[A]) 그리고 11의 배수부터는 $$11>\sqrt {100}$$이기 때문에 역시 지울 필요 없다.
이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는다. 이것이 100 이하의 소수이다.
이런 방법으로 만약 n이하의 소수를 '''모두''' 찾고 싶다면 1부터 n까지 쭉 나열한 다음에(...) 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.
일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우[3] 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로[4] 에라토스테네스의 체보다 빠른 방법이 없다. [5] 프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시.
다만 에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안되게 빠른방법이 넘쳐난다.
한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 어떤 수 $$m=ab$$라면 $$a$$와 $$b$$ 중 적어도 하나는 $$\sqrt{n}$$이하이다. 즉 n보다 작은 합성수 m은 $$\sqrt{n}$$보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, $$\sqrt{n}$$ 이하의 수의 배수만 지우면 된다. 단적으로 1~100인 위의 경우, 사실은 7의 배수 중 남아있는 49(7*7), 77(7*11), 91(7*13)만 더 지우면 끝난다. 만일 표에 11²(121)보다 큰 수가 있다면 11을 제외한 11의 배수를 지워야 하는데, 이 과정에서 최초로 지워지는 수는 121(11²)이다. 그런데 이는 주어진 범위를 초과하는 수다.

3. 여담

---

마지막 구호 생략 문서에 의하면, 에라토스테네스의 체를 머릿속에서 즉각적으로 실행해야 하는 '소수 생략'이라는 가히 정신나간 지시를 했다는 증언이 있다.
리만 가설 문서를 참고하면 좋다.

4. 관련 문서

---

• 노가다(수학)
• 에라토스테네스
• 정수론
  • 소수(수론)

[1] $$\bold{1}_{\mathbb{P}}(x)$$는 $$x$$가 소수이면 1, 그렇지 않을 경우 0의 값을 띠는 판별 함수이다. 그래서 소수가 아닌 수는 정의역에서 제외된다.

[2] 변형하여 O(n)의 시간복잡도를 이룰 수 있다.

[A] A B C D 4의 케이스만 봐도 알 수 있겠지만, 이미 지워진 수는 모든 배수가 앞선 케이스에서 지워졌기 때문에 검사할 필요 없이 그냥 패스하면 된다. 즉 검사 범위가 커지면 커질수록 지워지는 숫자가 많아지기 때문에 검사 횟수가 줄어든다.

[3] 예를 들어 정수 N이 주어지고 N 이하의 모든 정수를 검사해야 하는 경우. 이런 식의 문제에서 N은 다섯 자리 이상을 훌쩍 넘어가기도 하기 때문에 이런 단축 방법을 모르면 답이 없다.

[4] 윌런스의 공식이 있긴 하지만 너무 비효율적이라 소수를 찾고싶으면 그냥 노가다로 나눠보든가 해야 한다.

[5] 사실 작은 범위에 대해 먼저 체를 쓴 다음 그 체로 합성수를 미리 거르는 wheel이란 기법을 쓰면 좀더 빨라지긴 한다. 대개 60을 쓴다.