소수 구하기 (에라토스테네스의 체)

소수 구하기 - 에라토스테네스의 체

소수 구하기 문제는 2분류로 나눌 수 있다.

1. 소수의 개수를 구하는 문제

2. 소수 구하기 문제

소수를 구하는 방법에 대해 찾아보던 중 새로운 방법을 알게 되었다.

에라토스테네스의 체

소수는 1과 자기 자신으로만 나누어 떨어지는 수를 말한다.

즉, 2의 배수, 3의 배수, n의 배수는 소수가 될 수 없다.

에라토스테네스는 다음과 같이 소수를 구하였다.

예를 들어, 20이하의 수에서 소수를 구해 본다.

1. 2의 배수를 제외한다.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2. 3의 배수를 제외한다.

2 3 5 7 9 11 13 15 17 19

3. 5의 배수를 제외한다.

2 3 5 7 11 13 17 19

4. 20 이하의 수에서 소수는 다음과 같다.

2 3 5 7 11 13 17 19

즉, N보다 작은 수에서 소수를 구한다면, N보다 작은 소수의 배수를 모두 지우면 소수를 구할 수 있다.

소스코드에서 핵심은 n의 제곱이 구하고자하는 범위보다 작은경우까지 계산을 하는 것이다.

 

출처 : http://terms.naver.com/entry.nhn?docId=1179083&cid=40942&categoryId=32204