소수 찾아내는 알고리즘

소수를 찾아내는 알고리즘에는 크게 두가지 방법이 있다.

1. 무식하게 약수의 갯수를 구하는 방법

2. 에라토스테네스의 체를 이용하여 푸는 방법

에라토스테네스의 체를 이용하여 푸는 방법의 원리는 다음과 같다.

- 2부터 n까지의 수를 쭉 적고, 목록에서 지워지지 않는 수들을 순회함, 수의 배수를 지우기를 반복하다가

그 다음으로는 3의 배수를 모두 지우고, 5의 배수를 지우고, 7의 배수를 지우고... 쭉 제거를 하다 보면

남는 수들이 있는데 이를 체로 거른 뒤 남는 수들이 모두 결국 소수가 된다.

(그림 출처 : http://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

체를 이용하여 연산할 경우 부하가 확 줄어드니 한번쯤 적용해서 풀어보는 것도 좋을 것 같다.