[C/C++] 프로젝트 오일러 #46 : 골드바흐의 다른 추측

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

 

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

 

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

---

 

Project Euler 문제 46번, Goldbach’s Other Conjecture는 다음과 같은 내용을 다룹니다.

이 문제에서는 골드바흐의 다른 추측(Goldbach’s Other Conjecture)을 검증하는 과정에서 예외가 발생하는 가장 작은 홀수 합성수를 찾는 것이 목표입니다. 골드바흐의 다른 추측은 다음과 같습니다.

“모든 홀수 합성수는 어떤 소수 하나와 두 배의 어떤 제곱수의 합으로 나타낼 수 있다.”

즉, 홀수이며 합성수인 자연수  n 에 대해, 어떤 소수  p 와 자연수  k 가 존재하여 다음의 관계식을 만족한다고 합니다.

\[n = p + 2 \times k^2\]

이제 문제의 핵심은, 위의 관계식을 만족하지 않는 가장 작은 홀수 합성수를 찾는 것입니다.

---

이를 해결하기 위해, 먼저 홀수 합성수를 생성하고, 각 수에 대해 위 식을 만족하는  p 와  k 를 찾는 방식으로 접근해야 합니다. 만약 어떤 홀수 합성수가 위의 식을 만족하지 않는다면, 그것이 문제에서 찾고자 하는 정답이 됩니다.

이를 프로그래밍적으로 구현하면, 먼저 소수를 판별하는 알고리즘이 필요하며, 그다음으로 특정한 수가 위의 식을 만족하는지 여부를 확인하는 절차가 필요합니다. 효율적인 탐색 방법을 사용하여 답을 도출하는 것이 중요합니다.

 

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

 

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

 

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

 

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

---

Goldbach's Conjecture

다음은 제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #46 - Goldbach's Other Conjecture
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#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;
}