Project Euler 41

Problem 41
1からnまでの数字が全て1回ずつ使われているn桁の数をpandigitalと呼ぼう。例えば、2143は4桁のpandigitalでまた素数でもある。
最も大きいn桁のpandigitalで素数である数は？
http://projecteuler.net/index.php?section=problems&id=41

pandigitalは1〜nの順列を結合すればよいです。Pythonは順列を簡単に出せます。大きい順に出すには次のようにすればよいでしょう。

from itertools import permutations
for a in permutations(range(3, 0, -1)):

    print reduce(lambda x, y: x * 10 + y, a),   # list -> number

321 312 231 213 132 123

順列を出すコードはライブラリを使わなくても簡単に書けます。

def gen_perm(a, k = 0):

    if k == len(a) - 1:

        yield a

    else:

        for n in range(len(a)):

            for a2 in gen_perm(a[:n] + a[n+1:]):

                yield a[n:n+1] + a2
for a in gen_perm(range(3, 0, -1)):

    print reduce(lambda x, y: x * 10 + y, a),   # list -> number

大きいほうから順に素数判定していけばよいです。9桁からはじめても答えは出るのですが、9桁は実は調べる必要はありません。9桁のpandigitalは、各桁を足すと45になるので9で割り切れるからです。8桁も同様です。結局7桁から調べることになります。

from itertools import permutations, takewhile, dropwhile, imap
def gen_prime_candidates():

    yield 2

    n = 3

    while True:

        yield n

        n += 2
def is_prime(n):

    for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):

        if n % p == 0:

            return False

    return True
def max_prime_pandigit_core(n):

    for a in permutations(range(n, 0, -1)):

        m = reduce(lambda x, y: x * 10 + y, a)

        if is_prime(m):

            return m

    return 0
def max_prime_pandigit():

    for m in dropwhile(lambda m: m == 0, imap(max_prime_pandigit_core,

            filter(lambda n: n * (n + 1) % 9 != 0, range(9, 0, -1)))):

        return m
print max_prime_pandigit()