에라토스테네스의체

[C++] 에라토스테네스의 체 , 소수판별을 위한 도구

에라토스테네스의 체는 소수판별을 하기 위한 간단하고도 강력한 방법입니다. 1,0과 영은 소수가 아니므로 2부터 판별을 시작합니다. 소수의 정의는 약수가 자기 자신과 1만을 가진 숫자입니다. 그러므로 2는 소수입니다. 하지만 2의 배수는 2를 약수로 갖기 시작하므로 소수의 조건에서 벗어나게 됩니다. 이러한 점을 이용해 빠르게 소수가 아닌 수를 false로 저장하는 방법입니다. int m[1001]; // 에라토스테네스의 체 배열 크기 지정 //2~999까지 소수판별을 하는 코드입니다. void eratos() { for(int i=2;i