에라토스테네스의 체 (Sieve of Eratosthenes)

 * 에라토스테네스의 체 (Sieve of Eratosthenes)

주어진 수 n 이하의 모든 소수를 아주 빠르게 구하는 방법
기원전 3세기, 수학자 에라토스테네스가 고안했다

 1. 소수를찾고
 2. 그 소수의 배수들을 지워버림
 3. 1, 2를 계속 반복했을 때 지워지지 않는 수들이 모두 소수임

어떤 수가 소수라면, 그 수의 배수들은 소수가 아니라는 사실을 이용
정확히는 그 수의 배수들은 반드시 합성수라는 성질을 이용한 것

합성수 : 소수가 아닌 수
1보다 크고, 약수가 1과 자기 자신 외에도 더 있는 수를 의미

시간 복잡도는 O(n log log n)으로 매우 효율적이다

..~~~~..

 * 간단한 구현 알고리즘

 1. 2~n까지의 숫자 나열. boolean []을 사용 (모두 true로 시작한다)
 2. 소수 찾기. 2~sqrt(n) 범위 안의 소수를 찾는다
 3. 찾은 소수의 배수를 지움. 배열에서 false 처리를 한다
 4. 남은 수들이 소수

..~~~~..