[알고리즘] 소수(prime number) 구하기, 에라토스테네스의 체

🟡 소수(prime number)

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

- 1과 자기 자신 외에 약수가 존재하지 않는 수

 

🟡 대량의 수의 소수 판별 - 핵심 이론

- 대표적인 판별법: 에라토스테네스의 체

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

① 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.

② 2부터 시작하고 현재 숫자가 지워지지 않았을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다.

③ 배열의 끝까지 ②를 반복한 후(가장 큰 수의 제곱근까지만 연산하면 된다.) 배열에서 남아 있는 모든 수를 출력합니다.

- 예시

1에서 30까지의 수 중 소수 구하기
1. 배열 생성하기
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

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

3. 2를 선택, 2의 배수를 모두 삭제(2는 지우지 않는다)
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29

4. 3을 선택, 3의 배수를 모두 삭제(3은 지우지 않는다)
2 3 5 7
11 13 17 19
23 25 29

5. 5를 선택, 5의 배수를 모두 삭제(5는 지우지 않는다)
2 3 5 7
11 13 17 19
23 29

계속하여 지워지지 않는 수를 찾아 반복한다.
그 후 삭제되지 않은 수를 모두 출력
2 3 5 7
11 13 17 19
23 29

 

🟡 에라토스테네스의 체 시간 복잡도

- 이중 for문을 사용하므로 O(N^2)라고 생각할 수 있다

- 그러나, 일반적으로 O(Nlog(logN))이다.

- 왜냐하면 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문

 

 

 

🟡 단일 숫자의 소수 판별 - 탐색 범위

- 2부터 (자기자신 -1) 까지 하나하나 나눠보고, 나누어 떨어지는 수가 하나라도 생기면 그 수는 소수가 아니다.

- 그러나 구하고자 하는 수가 N이라 한다면, 탐색 범위는 N의 제곱근까지다.

- 이유

N이 a*b라 가정하면,
a와 b가 둘 다 N의 제곱근 보다 큰 상황은 존재하지 않는다.
N = (N의 제곱근 보다 작은 수) * (N의 제곱근 보다 큰 수)

ex) N = 12
루트 12 = 약 3.464

12를 만드는 약수의 쌍
1 * 12
2 * 6
3 * 4

두 수가 모두 12의 제곱근보다 큰 경우는 존재하지 않는다.