소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데, 그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ 이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 만약 있다면 댓글 달아주시기 바람. 요번에는 c++로 구현해보았음. 1. 알고리즘 에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다. 아래 그림을 보면 무엇인지 알 수 있다. 120까지의 모든 소수를 구한다고 해보자. 2부터 120까지 배열에 모두 넣은 후 소수가 아닌 것들을 모두 체크해버리는 것이다. 2를 제외한 모든 2의 배수를 체크한다. 3을 제외한 모든 3의 배수를 체크한다. 4는 아까 체크당했으므로 소수 ..
