[java] 소수 구하기 - 에라토스테네스의 체

 

에라토스테네스 체

• 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다.

일단 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의 배수를 제거한다.

	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의 배수에서 이미 지워졌다)
그러면 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,9는 2의배수,3의 배수 이기 때문에 수행할 필요가없다.

• 11부터는 11에1~9사이의 값을 곱한 것인데 이 또한 1~9의 배수들이기 때문이다.