에라토스테네스의 체

• 상위 항목 : 소수, 정수론. 노가다, 마지막 구호 생략

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

소수를 찾는 가장 간단한 방법이자 가장 무식한미개한 방법이다. 그 방법은 다름아닌 직접 나누기. 예를 들어 1~50까지의 소수를 찾는다 하자.

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

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

일단 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

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

뭔가 많이 줄어든 것 같은데 이거 맞다.

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

	2	3		5		7
11		13				17		19
		23		25				29
31				35		37
41		43				47		49

4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 2,3 다음으로 남아있는 가장 작은 수, 즉 5의 배수를 5를 제외하고 지우자.

그리고 마지막으로 7의 배수까지 지워제끼면,

	2	3		5		7
11		13				17		19
		23						29
31						37
41		43				47

이런 식으로 남은 것들의 2배수, 3배수,...n배수를 지우다보면 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47이 남는다. 이것이 50미만의 소수이다.

이런 방법으로 만약 n이하의 소수를 모두찾고 싶다 하면 1부터 n까지 쭉 나열한 다음에(...) 2의 배수, 3의 배수, 5의 배수...쭉쭉 나누는 것이다.

사실 소수를 '찾는 방법'이라기엔 좀 뭐한게... 합성수를 지우면 당연히 나머지가 남는다(...)

아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로, 소수를 찾고싶으면 그냥 노가다로 나눠보든가 해야한다.

한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 어떤 수 [math]m=ab[/math]라면 [math]a[/math]와 [math]b[/math] 중 적어도 하나는 [math]\sqrt{n}[/math]이하이다. 즉 n보다 작은 합성수 m은 [math]\sqrt{n}[/math]보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, [math]\sqrt{n}[/math]이하의 수의 배수만 지우면 된다. 단적으로 1~50인 위의 경우, 사실은 7의 배수 중 남아있는 49 하나만 더 지우면 끝난다.

마지막 구호 생략과 어쩐지 관련있을지도 모른다 (?)

리만 가설 문서를 참고하면 좋다.