Project Euler Problem 041

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

n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである.
例えば2143は4桁のPandigital数であり, かつ素数である.
n桁のPandigitalな素数の中で最大の数を答えよ.

最大の数を探せば良いので、大きい方からGreedyに探す。時間は結構かかる。

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 euler041():
    result = 0
    
    for i in xrange(9, 0, -1):
        for j in itertools.permutations(xrange(i, 0, -1)):
            if j[-1] % 2 and j[-1] % 5:
                val = reduce(lambda a, b: a * 10 + b, j)
                if is_prime(val):
                    result = val
                    break
        if result: break

    print result
    

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

答え: 7652413
実行時間: 0.772542秒くらい