[알고리즘] 에라토스테네스의 체

에라토스테네스의 체는 무엇인가?

에라토스테네스의 체는 소수를 구하는 알고리즘으로, 범위 내의 소수를 판별할때 유용하게 사용되는 알고리즘이다.

소수를 마치 체로 걸러내는 방식과 유사하다고 하여, 에라토스테네스의 체라는 이름이 붙었다.

작동 원리

1. 1부터 N까지 숫자 배열을 생성한다.

2. 1은 소수가 아니니 제거한다.

3. 2부터 시작하여 그 수를 제외한 배수들을 다 제거한다.

4. 그 후 1씩 증가하여 남은 숫자들도 3번과 똑같은 방식으로 진행한다.

 

예를 들어, 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은 합성수도, 소수도 아니므로 제거한다.

	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	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도 똑같은 방식으로 진행한다.

	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

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

이후 같은 방식으로 계속 반복하다 보면, 다음과 같은 숫자만 남게된다.

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

이런식의 구조가 에라토스테네스의 체이다.

 

아래는 이를 시각적으로 표현한 이미지이다.

https://ko.wikipedia.org/wiki/에라토스테네스의_체

코드

import math

N = 10

nums = [True] * (N + 1)
nums[0] = nums[1] = False

for i in range(2, int(math.sqrt(N)) + 1):
    if nums[i]:
        for j in range(i*i, N + 1, i):
            nums[j] = False

for i in range(2, N + 1):
    if nums[i]: print(i)

아래는 필자가 해당 알고리즘을 처음 알게되었을 때, 들었던 궁금증에 대한 답을 작성하였다.

 

1. 에라토스테네스의 체에서 소수를 구할 때, 왜 √N까지만 반복문을 도는 걸까?

모든 자연수 N은 N = A * B 형태로 나타낼 수 있다.

이때 A와 B 둘 다 √N보다 크다면, A * B는 N보다 커지게 된다.

그러므로 N = A * B를 만족할 수 없다.

따라서 N = A * B를 만족하려면, 적어도 하나는 √N 이하의 수여야 한다.

즉, 어떤 수 N의 배수를 지울 때 √N 이하의 수만 고려해도 그 이상 수들의 배수는 이미 지워졌거나 지워지게 되어 있다.

이 때문에 √N까지만 반복하면 효율적으로 소수를 판별할 수 있다.

 

2. 소수의 배수를 제거할 때, 왜 시작 지점이 i² 인가?

 

사실 이 질문은 에라토스테네스의 체 원리를 이해했다면 나올 수 없는 질문이었다.

하지만 필자는 이에 대한 이해도가 낮은 상태여서 이런 궁금증이 있었다.

 

x가 자연수이고 i의 배수일 때, (i < x < i²) 에 해당되는 x는 이미 이전의 소수에 의해 걸러진 합성수이기 때문이다.

	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부터 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의 배수는 3, 6, 9, ... 99 가 포함된다.

하지만 6은 이미 2에서 제거되었으므로, 3의 제곱인 9부터 진행한다.

	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

5 또한 마찬가지로 5를 제외한 5의 배수 중 남아있는 가장 작은 수는 25이다.

이처럼 i² 부터 시작해서 제거하는 것이 더 효율적이다.