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

 

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

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

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

 

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

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

 

 

1. 소수 식별

 

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

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

 

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

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

 

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

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

 

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

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

 

?

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

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; }

 

이를 활용하여 아래와 같이 간단한 함수를 만들면 대단히 빠른 속도로 소수 여부를 확인할 수 있다.

 

?

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

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$

 

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

 

?

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

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; }