에라토스테네스의 체는 소수판별을 하기 위한 간단하고도 강력한 방법입니다.
1,0과 영은 소수가 아니므로 2부터 판별을 시작합니다. 소수의 정의는 약수가 자기 자신과 1만을 가진 숫자입니다. 그러므로 2는 소수입니다. 하지만 2의 배수는 2를 약수로 갖기 시작하므로 소수의 조건에서 벗어나게 됩니다. 이러한 점을 이용해 빠르게 소수가 아닌 수를 false로 저장하는 방법입니다.
int m[1001]; // 에라토스테네스의 체 배열 크기 지정
//2~999까지 소수판별을 하는 코드입니다.
void eratos() {
for(int i=2;i<1000;i++) {
if(m[i]==1)continue;
for(int k=i+i;k<1000;k+=i){
m[k]=1;
}
}
}
판별해야할 숫자가 소수가 아니라면, 그 다음 숫자부터 모두 소수가 아니라고 값을 1로 넣어주는 코드입니다.
소수를 판독하는 코드가 없는데 ... 소수만 남는 것 맞나요? 라고 생각이 들 수도 있습니다. 하지만 2라는 소수로 시작해서 , 2를 약수로 갖는 모든 소수가 아닌수를 소수가 아니라는 값으로 1 을 넣어주고, 3이라는 소수를 if(m[i]==1)continue; 코드로 판독하고 3의 배수를 모두 체크해줍니다. 그러면 자연스럽게 숫자 4를 판독하여 에라토스테네스의 체를 실행할지 말지 결정할때, 숫자 4는 약수 2를 추가로 갖는 소수가 아닌 수라는 결론이 숫자 2를 실행하며 얻었기에, 바로 다음 숫자 5를 검사하기 위해 continue가 실행됩니다 !
출력결과
2 3 5 7 11
13 17 19
23 29 31
37 41
43 47
53 59 61
67 71
73 79
83 89
97 101
103 107 109
113 127 131
....
947 953
967 971 977
983 991 997
정확하게 소수만 출력되는 모습을 보실 수 있습니다.
위의 2중 for문에서 for문 횟수를 더 줄일려면
루트 n(검사해야할 숫자) 까지만 나누어서 떨어지면 소수가 아닙니다. 라는 성질을 이용해 줄일 수 있습니다.
void eratos() {
for(int i=2;i<sqrt(1000);i++) {
if(m[i]==1)continue;
for(int k=i+i;k<1000;k+=i){
m[k]=1;
}
}
}
C++ <math.h>의 제곱근 함수 sqrt()를 이용해 구해야할 소수범위에 적용시켜주면 됩니다.
숫자 50000까지 에라토스테네스의 체를 사용한다 했을때 시간차이는 환경에 따라 차이가 있겠지만
제곱근 방식을 사용하지 않은 for문은 0.000723~0.00048의 시간
제곱근 방식을 사용하면 0.000282 ~ 0.0004 까지의 시간이 나온다. (여러번 실행했을때 나오는 범위)
'알고리즘 개념 및 Tool C++' 카테고리의 다른 글
[C++] permutation을 이용한 조합과 순열 활용 (0) | 2021.05.24 |
---|