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

Sieve of Eratosthenes 수학에서 소수를 찾기 위한 방법중 하나로 고대 그리스 수학자 에라토스테네스가 고안한 방법이다. Prime(소수) 소수는 '양의 약수를 2개만 갖는 자연수' 즉, 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수로 자기자신과 1의 곱으로만 나타낼수 있는 1보다 큰 자연수를 말한다. Algorithm 해당 에라토스테네스는 자신보다 작은 두개의 자연수를 곱하여 만들수 없다는 성질을 이용한다. 2는 명확히 소수임을 알수 있고 2의 배수는 모두 위의 소수조건을 만족하지 못하므로 소수가 아님을 알 수 있다. 3은 2로 인해 지워지지 않았으므로 3보다 작은수의 배수가 아님을 알 수 있고 즉 소수임을 확인할 수 있으며 3의 배수는 소수가 아니므로 3의 배수 또한..