소수 판별법

소수인지 합성수인지의 판별

이전 게시글 처럼, 약수 세기와 같음
1부터 N까지의 수로 N을 나누어 본다
혹은 √N 까지의 수로 나누어 본다

이보다 좋은 방법은 없나?

에라토스테네스의 체

2부터 N까지 적는다
발견된 가장 작은 소수로, 그 배수를 지운다
(즉 2,3,5,7,11 ... 의 배수를 죄 지움 )