[정수론] 에라토스테네스 - 체 (소수 구하기)

소수란?

자신보다 작은 2개의 자연수를 곱해서 만들수 없는 1보다 큰 자연수

즉, 1과 자기 자신 외에 약수가 존재하지 않는 수를 뜻함

---

에라토스테네스 체 기법

소수를 구하는 대표적인 판별법

 

원리

1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성
2. 2번째 부터 시작하며, 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움 (처음 선택한 숫자는 지우지 않음)
3. 배열 끝까지 2. 을 반복한 후 배열에 남아 있는 모든 수를 출력한다.

---

▼ 탐색과정 ▼ (1부터 30까지의 수 중 소수를 구한다.)

 

① 주어진 범위 까지 배열을 생성 (1은 소수가 아니므로 삭제하고 2부터 시작)

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
16	17	18	19	10	21	22	23	24	25	26	27	28	29	30

 

②  선택한 수의 배수를 모두 삭제 (현재 선택된 수가 2이므로 2의 배수 모두 삭제)

1	2	3	4 ✓	5	6 ✓	7	8 ✓	9	10 ✓	11	12 ✓	13	14 ✓	15
16 ✓	17	18 ✓	19	10 ✓	21	22 ✓	23	24 ✓	25	26 ✓	27	28 ✓	29	30 ✓

 

③ 지워지지 않은 수 중 이전에 선택한 수(2)의 다음 수 선택 (이미 지워진 수를 제외하고 선택된 수 3의 배수를 삭제) 

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

 

④ ③과정과 같이 3 다음의 지워지지 않은 수 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

 

⑤  7, 11, 13의 배수는 이미 앞에서 선택한 수에 의해 모두 제거되었음.

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

 

⑥  17부터 선택되는 수 17, 19, 23은 자신을 제외한 각 배수가 30이상 이므로 제거할 값이 없음.

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

 

⑦  마지막 까지 배열에서 제거되지 않은 수가 지정한 범위에 존재하는 소수가 된다

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

 

 1 ~ 30 범위의 소수는 아래와 같다.

2

3

5

7

11

13

17

19

23

29

 

---

시간복잡도 

이중 for문을 이용하므로 O(N²) 정도라고 판단한다.

실제 시간복잡도는 일반적으로 O(Nlog(logN)) 이며 (최적화 정도에 따라 다를 수 있음)

이는 배수를 삭제하는 연산으로 실제 구현시 바깥 for문 을 생략하는 경우가 빈번하게 발생하기 때문이다.

내부 for문으로 배수를 제거하며 외부for문은 다음 배수의 선택하는 용도로 사용된다.

이때, 외부for문을 통해 다음 배수 선택 시 내부 for문에 의해 이미 제거된 배수는 배열에서 제거되므로 재삭제 되지 않기 때문에

뒤로 갈 수록 이미 배수로 제거된 요소들은 외부for문에서 다음요소로 사용되지 않게된다.

`외부 for문은 1부터 30이 아니라 내부for문이 돌고 난 뒤에 남아있는 배열 요소를 순차적으로 탐색하도록 범위를 reset해줘야함`

따라서 O(N²) 이지만 생략요소로 인해 N * log(logN)인 Nlog(logN)이라고 가정할 수 있다.

 

이러한 원리로 코딩테스트에서 소수를 구하는 일반적인 방법으로 에라토스테네스의 체 기법이 통용적으로 사용된다.