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

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

 

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

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

 

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

 

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

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

 

 

0. 에라토스테네스의 체

 

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

 

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로 나눠보고... 하는 것이다.

 

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씩 증가시키면 조금은 더 빨라진다.

 

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. 비교를 위해 식별하려는 매 숫자마다 일일이 알고리즘을 다시 돌렸다는 의미임 [본문으로]