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秒くらい