에라토스테니스의 체

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

체크할 때, 모든 수를 다 돌면서 체크할 필요 없이 체크 할 배수만큼만 반복문을 돌게하는 것이다.

 

그리고, 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다.

(왜냐면, 체크된 수의 배수들도 이미 다 체크가 되어있기 때문이다)

 

[C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체