소수찾기 알고리즘
2부터 시작해서 배수가 되는 수를 지워나가면 다 지우고 최종적으로 남은 수들이 소수가 된다.
소수가 아닌 수를 걸러내는 것이 체로 걸러내는 모양과 비슷해서 '에라토스테네스의 체' 라고 부름
시간 복잡도 : O(N*log(logN))
알고리즘 :
1. 2부터 N까지 소수를 구하고자 하는 범위의 모든 수를 나열
2. 2를 제외한 2의 배수를 모두 지움
3. 3을 제외한 3의 배수를 모두 지움
4. 5를 제외한 5의 배수를 모두 지움
...
?. n을 제외한 n의 배수를 모두 지움
(여기서 n은 n*n<=N 을 만족하는 소수 <- 이유는 뒤에서 설명)
최종적으로 지우지 않고 살아남은 수들이 소수가 됨
boolean형 prime 배열을 사용한다.
- true이면 소수
- false이면 소수가 아님
알고리즘 설명 :
[예제]
N을 120이라고 하자.
1부터 120까지 수 중에서 소수를 찾아라.
<1>
먼저, 2를 제외한 2의 배수를 모두 제거한다.
<2>
3을 제외한 3의 배수를 모두 제거한다.
<3>
5를 제외한 5의 배수를 모두 제거한다.
<4>
7을 제외한 7의 배수를 모두 제거한다.
<5>
11은 prime[11]=true 로 소수이지만,
11*11 = 121은 120보다 크므로 반복문이 종료됨
그러므로 최종으로 남은 수들이 1부터 120까지 중에서 소수가 된다.
Q. 그렇다면 왜 n*n<=N 을 만족할 때까지 반복하는 것일까? (이 조건이 왜 생겨났을까?)
여기서 일단 n은 소수이다.
위의 과정대로 n을 제외한 n의 배수를 모두 제거한다고 할 때,
n*2 는 앞선 2의 배수를 제거하는 과정에서 이미 지워졌다. (n*2는 n의 배수이지만, 2의 배수이기도 하니까)
n*3 은 앞선 3의 배수를 제거하는 과정에서 이미 지워졌다. (n*3은 n의 배수이지만, 3의 배수이기도 하니까)
n*5 는 앞선 5의 배수를 제거하는 과정에서 이미 지워졌다. (n*5는 n의 배수이지만, 5의 배수이기도 하니까)
...
이처럼 n과 곱해지는 값이 n 이전의 수일때는, 이전 과정에서 이미 지워졌을 것이다.
그렇다면 남은 것은 n*n이다.
n*n은 n의 배수를 제거하는 과정을 거치지 않았으므로 소수이냐 아니냐를 판정해야 한다.
n*n가 N(위 예제에서는 120)보다 크다면, 범위를 벗어났으므로 굳이 소수인지 아닌지 고려할 필요가 없다.
그래서 n*n<=N 이면 반복문을 돌아서 n*n가 소수인지 아닌지 판정하고,
n*n>N 이면 굳이 반복문을 돌지 않고 종료한다.
알고리즘 코드 :