[코딩테스트] 자바 Java, 에라토스테네스의 체: 소수 찾기

에라토스테네스의 체 Sieve of Eratosthenes

• 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법
• 마치 체로 치듯 수를 걸러내가며 소수를 찾아가는 방법
• 특정 범위 내의 소수를 찾는 방법
• 완전 탐색(일종의 노가다 방식)이라 무식한 방법이지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우 이보다 빠른 방법이 없음. 다만,  '특정 범위 내의 소수'를 판정하는 데에만 효율적

 

소수 Prime Number

• 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
• 2, 3, 5, 7, 11, ...

 

방법

1. 범위 내의 모든 수 나열
2. 소수도, 합성수도 아닌 1부터 제거
3. 2부터 차례대로 소수인 n의 배수를 모두 제거
4. 주어진 범위가 k라면 √k보다 작은 소수들에 한하여 3.의 과정 반복
   • √k 이상의 소수 n의 경우 이후 n의 배수들은 이미 이전 소수에서 지워진 수이거나 최초로 지워지는 수가 범위를 초과하는 수이기 때문에 멈춤
     • 예를 들어, 주어진 범위가 100인 경우 √100 = 10이므로 10 이하의 소수의 배수만 체크하면 됨!
     • 100까지 범위 안의 소수 중, √100인 10 이상의 첫 번째 소수 11의 배수의 최초로 지워지는 수는 121이기 때문에 범위를 초과 함!
5. 남은 수들이 범위 내의 소수이다 ! ! !

예시: 100의 소수 찾기

1) 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

2) 소수도, 합성수도 아닌 유일한 자연수 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의 배수 제거

	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의 배수 제거

	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) 4의 배수는 이미 2의 배수이기 때문에 건너뛰고, 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

4) 6의 배수는 이미 2의 배수이기 때문에 건너뛰고, 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

5) 이후 부터는 지울 필요x, 남은 값들이 100 이하의 소수

 - 이미 앞의 소수들의 배수임으로 이미 지워졌기 때문

 - 11 이상의 소수들의 배수부터는 11 > (√100 = 10)이기 때문

 

---

참고 및 출처

나무위키: 에라토스테네스의 체