Project Euler Problem 046 - つまみ食う

http://projecteuler.net/index.php?section=problems&id=46
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

   9 =  7 + 2 * 1^2
  15 =  7 + 2 * 2^2
  21 =  3 + 2 * 3^2
  25 =  7 + 2 * 3^2
  27 = 19 + 2 * 2^2
  33 = 31 + 2 * 1^2

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.

まず、言葉がわからないのでググる。

「合成数」ってのは自然数で 1とその数自身以外の約数をもつ数らしい。素数でない数ってことか。
「奇合成数」はそれの奇数ってことみたい。

なので

奇数のみ調べる
調べる数が素数なら素数リストへ
調べる数が素数でないなら素数リストの数を引き算したのち2で割ったのが平方数かどうか調べる

という方法でいけそう。

import math
import itertools
import datetime


def is_prime(n):
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False
    if n < 9: return True
    if n % 3 == 0: return False
    
    r = math.floor(math.sqrt(n))
    f = 5
    while f <= r:
        if n % f == 0: return False
        if n % (f+2) == 0: return False
        f += 6
    return True


def is_ChristianGoldbach_proposed(n, primes):
    it = iter(primes)
    
    for i in it:
        j = math.sqrt((n - i) / 2)
        if int(j) == j:
            return True
    return False


primes = [ ]

def euler046():
    i = 3
    result = 0
    
    while True:
        if is_prime(i):
            primes.insert(0, i)
        else:
            if not is_ChristianGoldbach_proposed(i, primes):
                result = i
                break
        i += 2

    print result        


begin = datetime.datetime.now()
euler046()
end = datetime.datetime.now()
print end - begin

答え: 5777
実行時間: 0.021927秒くらい