java 알고리즘

[알고리즘] 에라토스테네스의 체 고대 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법으로 2를 제외한 2의 배수, 3을 제외한 3의 배수, 5를 제외한 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다. 마치 체로 치듯이 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다. 이는 자연수 N에 대해서 그 이하의 수 중에서 소수를 찾는 가장 빠른 방법이다. 방법 1부터 N까지 소수를 구하고자 하는 구간의 모든 수를 쭉 나열한다. 우선 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다. 남은 수 가운데 가장 작은 수를 제외한 배수를 모두 지운다. 3번 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 위의 2번 과정을 조금 더 풀어서 흐름이 어떻게 진행되는지 살펴보자...