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

에라토스테네스의 체란?

에라토스테네스가 만든 소수 판정방법으로, 쉽게 얘기해서 숫자들 중 소수를 체에 걸러서 찾아내는 방법입니다.

 

 

사용 이유

10까지의 소수는 그냥 찾기 쉽지만, 10000000까지의 소수는 찾기 쉽지 않다. 

이럴 때 에라토스테네스의 체를 이용해서 효율적으로 소수를 찾아냅니다.

 

사용방법

특정한 수 n까지 소수를 구하고 싶다면,

2부터 n까지 2의 배수를 모두 제거한다...(자신인 2를 제외하고)

3부터 n까지 3의 배수를 모두 제거한다...(자신인 3을 제외하고)

4부터 n까지 4의 배수를 모두 제거한다....(자신인 4를 제외하고)

....

...

n부터 n까지 n의 배수를 모두 제거한다.. (자신인 n은 제거하지 않으므로 아무것도 제거하지 않음)

 

모두 제거하고 남은 수가 소수입니다.

 

예제 ) 15까지의 소수 찾기

1은 소수가 아니므로,

2부터 시작해서 2의 배수 4,6,8,10,12,14를 제거합니다.

3부터 시작해서 3의 배수 6,9,12,15를 제거합니다.

4....     8,12를 제거합니다.

5....     10,15를 제거합니다.

6....     12를 제거합니다.

7....     14를 제거합니다.

 

.....

 

15....   는 제거할 값이 없습니다.

 

따라서 남은 수인

2
3
5
7
11
13

가 소수입니다.