[중Ⅰ 소인수분해] 에라토스테네스의 체

[정의]

 

'에라토스테네스의 체'는 소수를 찾아내는 방법입니다.

---

[배수의 개념 이용하기]

 

2의 배수가 있다고 해봅시다.

2의 2배수는 4고, 2의 3배수는 6입니다.

2에 곱을 해나간 것이 배수란 말입니다.

거꾸로 생각해보면 어떤 수의 2배수 이상은 어떤 수로 나누어지기 때문에 1과 자신이외의 수로 나눌 수 있는 경우에 해당합니다.

 

즉, 어떤 수의 배수는 합성수입니다.

'에라토스테네스의 체'는 바로 이런 배수의 개념을 이용한 것입니다.

---

[적용순서]

 

① 1을 지운다.
② 2는 남기고 2의 배수를 모두 지운다.
③ 3은 남기고 3의 배수를 모두 지운다.
④ 5는 남기고 5의 배수를 모두 지운다.
⑤ 이와 같은 방법으로 남은 수 중에서 처음 수는 남기고 그 수의 배수를 모두 지운다.

---

[적용과정]

 

① 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	14	15	16	17	18	19	20
21		23	24	25	26	27	28	29	30
31		33	34	35	36	37	38	39	40
41		43	44	45	46	47	48	49	50
51		53	54	55	56	57	58	59	60
61		63	64	65	66	67	68	69	70
71		73	74	75	76	77	78	79	80
81		83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

---

③ 3은 남기고 3의 배수를 모두 지운다.

 

	2	3		5		7
11		13	14		16	17	18	19	20
		23	24	25	26		28	29	30
31			34	35	36	37	38		40
41		43	44		46	47	48	49	50
		53	54	55	56		58	59	60
61			64	65	66	67	68		70
71		73	74		76	77	78	79	80
		83	84	85	86		88	89	90
91	92		94	95	96	97	98		100

---

④ 5는 남기고 5의 배수를 모두 지운다.

 

	2	3		5		7
11		13	14		16	17	18	19	20
		23	24	25	26		28	29	30
31			34	35	36	37	38		40
41		43	44		46	47	48	49	50
		53	54	55	56		58	59	60
61			64	65	66	67	68		70
71		73	74		76	77	78	79	80
		83	84	85	86		88	89	90
91	92		94	95	96	97	98		100

---

⑤ 이와 같은 방법으로 남은 수 중에서 처음 수는 남기고 그 수의 배수를 모두 지운다.

표를 보니 이제 7을 남기고 7의 배수를 지울 차례입니다.

 

	2	3		5		7
11		13	14		16	17	18	19	20
		23	24	25	26		28	29	30
31			34	35	36	37	38		40
41		43	44		46	47	48		50
		53	54	55	56		58	59	60
61			64	65	66	67	68		70
71		73	74		76		78	79	80
		83	84	85	86		88	89	90
	92		94	95	96	97	98		100

---

다음은 11을 남기고 11의 배수를 지울 차례입니다.

지울 수는 22, 33, 44, 55, 66, 77, 88, 99 입니다.

 

다음은 13을 남기고 13의 배수를 지울 차례입니다.

지울 수는 26, 39, 52, 65, 78, 91 입니다.

 

다음은 17을 남기고 17의 배수를 지울 차례입니다.

지울 수는 34, 51, 68, 85 입니다.

 

다음은 19를 남기고 19의 배수를 지울 차례입니다.

지울 수는 38, 57, 76, 95 입니다.

 

다음은 23을 남기고 23의 배수를 지울 차례입니다.

지울 수는 46, 69, 92 입니다.

 

다음은 29를 남기고 29의 배수를 지울 차례입니다.

지울 수는 58, 87 입니다.

 

다음은 31을 남기고 31의 배수를 지울 차례입니다.

지울 수는 62, 93 입니다.

 

다음은 37을 남기고 37의 배수를 지울 차례입니다.

지울 수는 74 입니다.

 

다음은 41을 남기고 41의 배수를 지울 차례입니다.

지울 수는 82 입니다.

 

다음은 43을 남기고 43의 배수를 지울 차례입니다.

지울 수는 86 입니다.

 

다음은 47을 남기고 47의 배수를 지울 차례입니다.

지울 수는 94 입니다.

 

다음은 53을 남기고 53의 배수를 지울 차례입니다.

100안 의 자연수 중에 53의 배수는 없습니다.

그렇다면 그 다음 수는 53보다 더 클 테니 그 다음 수도 역시 배수가 없다는 것을 알 수 있습니다.

---

[적용결과]

 

지우고 남은 수는 다음과 같습니다.

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

 

결국 이렇게 1과 어떤 수의 배수인 수를 지우고 남은 수가 소수입니다.