46. 프로젝트 오일러 #46 : 골드바흐의 다른 추측

이번문제는 골드바흐의 소수에 관련된 오래된 추측과 모양만 유사한 문제입니다.

골드바흐의 추측은 당시 많은 수학자들의 예상을 깨고, 아직까지 증명되지 않은 문제입니다.  (홀수 완전수와 비슷하게 증명이 쉽게 이루어질거라는 예상을 깨고서 아직까지 증명되지 않았습니다.)

문제의 난이도는 5%로 상당히 낮습니다.  풀이 자체가 어렵지 않습니다.

문제를 살펴보면 다음과 같습니다.

영어를 해석하는 데 문제가 없다면, 이 문제를 푸는 데 어려움도 없을겁니다.

모든 홀수 합성수(1과 소수를 제외한 자연수)는 소수와 제곱수의 2배수의 합으로 표현이 된다는 추측입니다.  하지만 이 추측은 거짓으로 증명됩니다.

거짓이 되는 가장 작은 홀수 합성수는 얼마일까요?

이 문제는 그냥 단순하게 적용하면 별 무리 없이 풀 수 있습니다.

저는 소수를 구하면서 소수가 아닌 홀수에 대해서 위의 추측에 맞는 가를 검사했습니다.  소수의 갯수마다 모두 도는 것이기 때문에 속도가 느릴 수 있습니다만, 실제로는 측정할 수 없을 정도의 시간 안에 값이 나왔습니다.

다음은 제가 사용한 코드입니다.

#include <stdio.h>
#include <math.h>

int primes[10000];
int pcount = 0;

bool IsPrime(int n);
bool IsCG(int n);

int main()
{
    int ans;

    primes[pcount++] = 3;
    primes[pcount++] = 5;
    primes[pcount++] = 7;

    for( ans = 9 ; ; ans += 2 )
    {
        if( IsPrime(ans) ) { primes[pcount++] = ans; continue; }
        if( !IsCG(ans) ) break;
    }
    printf("ans = %d\n", ans);
}

bool IsPrime(int n)
{
    for( int i = 0 ; i < pcount ; i++ )
        if( n%primes[i] == 0 ) return false;
    return true;
}

bool IsCG(int n)
{
    for( int i = 0 ; i < pcount ; i++ )
    {
        int s = (n-primes[i])/2;
        int t = sqrt(s);
        if( t*t == s ) return true;
    }
    return false;
}