대각선에서 소수의 비율이 10% 이하가 되는 값 찾기

 

간만에 풀어보는 프로젝트 오일러.

이 문제는 복잡하게 생각하지 않아도 된다.

간단한 규칙만 찾으면 된다.

 

오히려 진짜 문제는 소수의 판별을 빠르게 하는 방법을 찾는 것.

에라토스테네스의 체를 활용하기 힘든 문제라 오히려 이 쪽이 성능에 영향을 미칠 수 있다.

 

 

1. 소수 식별

 

앞에서도 썼듯이, 소수를 식별하는 방법 중 에라토스테네스의 체보다 더 빠른 방식은 없다.

충분한 메모리만 확보할 수 있으면 이 방법이 최고다.

 

하지만, 이 문제에선 왠지 이 방식을 쓰는 게 어색하다.

대체 얼마만큼의 메모리를 확보해야 하는지를 알 수 없기 때문이다.

 

그래서 여기선 정공법을 선택했다.

정공법으로 풀 때 나누어지는지의 여부는 3 ~ \(\sqrt {n}\)까지만 확인하면 된다.

 

정수 범위에서 제곱근을 빠르게 구하는 방법은 위키피디아에서 찾을 수 있다.

이를 코드로 표현하면 아래와 같다.

 

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 IsPrime(unsigned num) {
    switch (num) {
    case 0: case 1: case 4: return false;
    case 2: case 3: case 5: return true;
    }

    if (!(num & 1)) { return false; }

    unsigned range = isqrt(num);
    if (range * range == num) { return false; }

    for (unsigned i = 3; i <= range; i += 2) {
        if (!(num % i)) { return false; }
    }
    return true;
}

 

 

2. 대각선에서 해당되는 값을 탐색하는 법

 

사실, 이 문제를 풀기 위해 커다란 사각형을 직접 그릴 필요는 없다.

첫 값인 1을 중심으로 증가되는 값들만 따라가도 규칙을 확인할 수 있다.

 

게다가, 오른쪽 아래 방향의 대각선은 굳이 따라갈 필요도 없다.

그 자리에 오는 값들은 제곱수이므로 소수가 나올 수 없다.

 

즉, 확인해야 되는 값은 아래와 같은 규칙으로 증가하는 값이다.

 

\((1) + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + \cdots\)

 

위를 토대로 작성해보면 아래와 같은 결과가 나온다.

 

int main()
{
    int n = 1;
    int plus = 0;
    int width = 1;
    int count = 0;

    while (true) {
        ++plus;
        n += plus;
        n += plus;
        if (IsPrime(n)) { ++count; }

        ++plus;
        n += plus;
        if (IsPrime(n)) { ++count; }
        
        n += plus;
        if (IsPrime(n)) { ++count; }

        width += 2;

        if (count * 10 < (width * 2 - 1)) { break; }
    }

    printf("width: %u, diagonal: %u, count: %u, ratio: %g%%\n", width, width * 2 - 1, count, (double)count / (width * 2 - 1) * 100);

    return 0;
}