http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2041
---
n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である.
n桁のPandigitalな素数の中で最大の数を答えよ.
---
Pandigitalな数を求めて、素数かどうか判定するだけ。
Pandigitalな数を階乗により求めるため、以下のようなソースを書いたが、もっとスマートな方法はありそう。
なお、1から9のPandigitalな数や1から8のPandigitalな数は、素数になりえない(※)ため除外してある。
※各桁の和が3の倍数に必然的になり、その結果必然的にその数自身も3の倍数になるためである。なお、1から2,3,5,6のPandigitalな数は同様の理由で除外される。また、1から1のPandigitalな数は、すなわち1であり、素数でない。よって、1から4なPandigital、もしくは1から7のPandigitalな数を考察すれば十分である。
def fac(x):
if x==1:
return 1
else:
return x*fac(x-1)
def is_prime(p):
j=2
while j * j<=p:
if not p % j:
return 0
j+=1
return 1
def gen_Pandigital(x,y):
max = fac(y)
n = max - 1
while n >= 0:
m = n
strs=''
arr = range(x,y+1)
for facs in fac_arr:
strs+=str(arr.pop(m // facs))
m %=facs
strs+=str(arr.pop())
yield strs
n -= 1
def get_prime(i):
for j in gen_Pandigital(1,i):
if is_prime(int(j)):
return j
return 0
if __name__ == '__main__':
for i in [7,4]:
fac_arr = [fac(i-l) for l in range(1,i)]
ans = get_prime(i)
if ans:
print ans
break