Project Euler Problem 049

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

項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。

  (i)3つの項はそれぞれ素数である。
  (ii)各項は他の項の置換で表される。

1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。

それではこの数列の3つの項を連結した12桁の数を求めよ。

とくに工夫なし。

import math
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 primelist(limit=1000):
    checked = [ True ] * ((limit-1)/2)
    result = [2]
    for i in xrange(len(checked)):
        val = i * 2 + 3
        if checked[i]:
            result.append(val)
            j = val + val + val
            while j < limit:
                checked[(j - 3) / 2] = False
                j += val + val
    return result


def contain(n):
    result = []
    while n:
        result.append(n%10)
        n /= 10
    result.sort()
    return result


def euler048():
    primes = primelist(10000-6660)
    
    for i in primes:
        if i < 1000: continue
        
        if contain(i) == contain(i+3330) == contain(i+6660):
            if is_prime(i+3330) and is_prime(i+6660):
                print i, i+3330, i+6660



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

答え: 296962999629
実行時間: 0.004150秒くらい