[Project Euler] 46. (소수 + 2×제곱수)로 나타내지 못하는 가장 작은 홀수인 합성수는?

46. (소수 + 2×제곱수)로 나타내지 못하는 가장 작은 홀수인 합성수는?

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

9 = 7 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

Click  

소수 판정은 에라토스테네스의 체로 어느정도 적정선을 구해놓고 하는게 좋겠지만 답을 구하기전에는 적정선을 모르니 일반 소수 판정을 약간 변형, 앞에서 구한 소수들을 이용했습니다.

<script language="Javascript" type="text/javascript">
/* 소수판정. 기존에 구한 소수 배열을 이용. */
function isPrime(n, prime){
    if(n==3) return true;
    for(var i=0; prime[i]*prime[i] < n; i++)
        if(n%prime[i] == 0)
            return false;
    return true;
}
/* 골드바흐의 홀수 합성수 추측 확인. 기존에 구한 소수 배열을 사용. */
function isGoldbach(n, prime){
    for(var i=0; i < prime.length; i++){
        var temp = Math.sqrt((n-prime[i])/2);
        if(temp == ~~temp)
            return true;
    }
    return false;
}
function p046(){
    prime = new Array();
    for(var i=3; ; i+=2){
        if(isPrime(i, prime))
            prime[prime.length] = i;
        else if(!isGoldbach(i, prime))
            break;
    }
    alert(i);
}
</script>

찾아보니 위의 경우와는 약간 다르지만 짝수와 관련 된 골드바흐의 추측이 있군요. 이 것은 아직 미해결 문제로 남아있다네요.

골드바흐의 추측(Goldbach's conjecture)은 오래 전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다.
이때 하나의 소수를 두 번 사용하는 것은 허용한다.
예를 들어, 20까지의 짝수는

4 = 2+2 6 = 3+3
8 = 3+5
10 = 3+7 = 5+5
12 = 5+7
14 = 3+11 = 7+7
16 = 3+13 = 5+11
18 = 5+13 = 7+11
20 = 3+17 = 7+13

위와 같이, 두 개의 소수의 합으로 표현할 수 있다. 그러나 모든 짝수에서 가능한지는 아직까지 해결하지 못하고 있다.

위키백과 : 골트바흐의 추측