Project Euler 41「パンデジタル素数」

itertoolsとも仲良くしていきたいですね。

Problem 41 「パンデジタル素数」

n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
例えば2143は4桁パンデジタル数であり, かつ素数である. n桁（この問題の定義では9桁以下）パンデジタルな素数の中で最大の数を答えよ.

from itertools import permutations

def hoge(num):
    # 大きい桁数から
    for n in range(num, 0, -1):
        d = '123456789'[:n]
        # パンデジタル数を大きい順に
        perm = sorted(permutations(d), reverse=True)
        for p in perm:
            i = int(''.join(p))
            if is_prime(i): return i

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return all(n % i != 0 for i in range(3, int(n ** 0.5) + 1, 2))

print(hoge(9))

python3とpython2.7で実行速度にかなりの差が出る。

xxx@xxx:~$ time python3 pe41.py
7652413
real    0m1.005s
user    0m0.956s
sys     0m0.048s
xxx@xxx:~$ time python pe41.py
7652413
real    0m23.992s
user    0m23.960s
sys     0m0.028s