소수를 구하는 알고리즘, 에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 아이디어는 다음과 같다. 만약 2부터 160사이의 소수를 찾는다고 해보자. 그러면 2와 160사이의 수에 다음과 같은 알고리즘을 적용한다. 1. 2는 소수이고, 2를 제외한 2의 배수는 소수에서 제외한다. 2. 3은 소수이고, 3을 제외한 3의 배수는 소수에서 제외한다. 3. (4는 2의 배수이므로 제외) 5는 소수이고, 5를 제외한 5의 배수는 소수에서 제외한다. 4. (6은 2의 배수에서 제외) 7은 소수이고, 7을 제외한 7의 배수는 소수에서 제외한다. 5. (8, 9 10 제외) 11은 소수이고, 11을 제외한 11의 배수는 소수에서 제외한다. 6. 12는 소수가 아니어서 제외되었다. 여기까지만 하면 2와 160사이의 소수를 구할 수 있다. 아이디어는 다음과 같다. 13과 160의 관계는 아래와 같다. 따라서 13보다 작은 수의 배수들만 지워도 충분히 소수를 구할 수 있다. 이를 자바로 작...

원문링크 : 소수를 구하는 알고리즘, 에라토스테네스의 체