정공법으로 소수 판별 시 더 빠른 방법은?

출처: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

 

앞 포스팅에서도 짧게 언급했는데, 소수 여부를 판별하는 가장 빠른 방법은 에라토스테네스의 체다.

수의 범위가 정해져있다면 그 범위까지의 소수를 모두 식별하는데 이것보다 빠른 방법은 없다.

 

하지만, 반대로 이 방식은 임의의 한 수가 소수인지 식별할 때는 오히려 느린 편이다.

 

일일이 숫자를 나눠서 확인하는 경우 더 빠른 방법이 어느쪽인지 테스트해봤다.

테스트 환경은 그냥 개인용 PC(AMD Ryzen 5 3600X)인데, 다른 환경이라고 큰 차이는 없을 듯.

 

 

0. 에라토스테네스의 체

 

그냥 지나치긴 뭐해서 일단은 간단히 구현해봤다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

bool IsPrime_0(unsigned num) {     switch (num) {     case 0: case 1: case 9: return false;     case 2: case 3: case 5: case 7: return true;     }       if (!(num & 1)) {         return false;     }           bool* t = (bool*)malloc((num + 1) * sizeof(bool));     memset(t, 0, (num + 1) * sizeof(bool));       for (unsigned i = 2; i < num; ++i) {         if (!t[i]) {             for (unsigned j = i * 2; j <= num; j += i) {                 if (j == num) {                     return false;                 }                 t[j] = true;             }         }     }       free(t);     return true; }

 

30만 이하의 소수 25,997개를 일일이 식별^[각주:1]해보니 소요 시간은 21.812초.

코드 특성상 그 이상의 숫자 범위에서는 메모리 오류가 발생할 수도 있다.

 

 

1. 3 ~ $\sqrt{n}$ 까지 증가시키며 나누기

 

앞 포스팅에서 사용한 방법인데, 일단 $\sqrt{n}$를 먼저 계산한 뒤 3부터 일일이 나눠본다.

이 때 루프를 줄이고, 효율을 올리기 위해 제수(divisor)를 범위 앞뒤에서 좁혀가면서 돌린다.

 

즉, 101이 소수인지 확인한다면 우선, 3과 11로 나눠보고, 다음은 5와 9로 나눠보고... 하는 것이다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

unsigned isqrt(unsigned num) {     unsigned res = 0;     unsigned bit = 1 << 30; // The second-to-top bit is set: 1 << 30 for 32 bits       // "bit" starts at the highest power of four <= the argument.     while (bit > num) { bit >>= 2; }       while (bit != 0) {         if (num >= res + bit) {             num -= res + bit;             res = (res >> 1) + bit;         }         else {             res >>= 1;         }         bit >>= 2;     }     return res; }   bool IsPrime1(unsigned num) {     switch (num) {     case 0: case 1: case 9: return false;     case 2: case 3: case 5: case 7: return true;     }       if (!(num & 1)) { return false; }       unsigned begin = 3;     unsigned range = isqrt(num) | 1;     //3 .. range     //5 .. range - 2       int count = ((range - 3) / 2 + 1 + 1) / 2;       for (int i = 0; i < count; ++i, begin += 2, range -= 2) {         if (!(num % begin) || !(num % range)) { return false; }     }     return true; }

 

이걸로 같은 범위인 30만 이하의 소수 25,997개를 찾아보니 소요 시간은 0.047초.

에라토스테네스의 체 보다 500배 가까이 빠르다[...]

 

 

2. $\sqrt{n}$ 계산 없이 제곱이 n인 범위까지 증가시키며 나누기

 

좀 다르게 생각해보면 굳이 n의 제곱근을 계산할 필요 없이, 범위의 제곱이 n일 때까지 증가시켜도 된다.

이 경우는 제곱근을 계산하는 부하가 줄어드는 대신에, 매 루프에서 범위를 확인해야 되는 새로운 부하가 추가된다.

 

루프의 수를 줄이기 위해 제수(divisor)를 4씩 증가시키면 조금은 더 빨라진다.

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

bool IsPrime2(unsigned num) {     switch (num) {     case 0: case 1: case 9: return false;     case 2: case 3: case 5: case 7: return true;     }       if (!(num & 1)) { return false; }       unsigned range = num / 3;     unsigned pos = 3;     while (pos <= range) {         if (!(num % pos) || !(num % (pos + 2))) { return false; }         pos += 4;         range = num / pos;     }     return true; }

 

이걸로 같은 범위인 30만 이하의 소수 25,997개를 찾아보니 소요 시간은 0.062초.

에라토스테네스의 체 보다 350배 정도 빠르다[...]

 

미세한 차이지만, 1번의 방법보다 조금은 느리다.

 

코드의 크기를 쪼금이라도 줄여야 되는 상황이면 2번, 그 외 대부분의 경우에선 1번을 사용하는 게 합리적일 듯.

 

 

1. 비교를 위해 식별하려는 매 숫자마다 일일이 알고리즘을 다시 돌렸다는 의미임 [본문으로]