プロジェクトオイラー
http://projecteuler.net/index.php
Q51.
例えば、56○○3の○に同じ数字を入れる。このとき7つが素数になる。○はいくつでもよい。素数が8つになる最小の整数。
0〜9を○に入れたうちの8つ以上が素数なので、少なくとも素数が3つ連続することになる。よって、少し考えると、隣との差は6の倍数でなければならないことが分かる。○の個数は3の倍数でなければならない。また、1の位は○であってはならない。
from itertools import count, permutationsdef is_prime(n):
if n == 1:
return False
elif n == 2:
return True
elif (n & 1) == 0:
return False
p = 3
while p * p <= n:
if n % p == 0:
return False
p += 2
return Truedef resolve(n):
a = [ ]
while n:
a.append(n % 10);
n /= 10
return adef unresolve(a):
n = 0
for i in reversed(a):
n = n * 10 + i
return ndef embed(a, b, d):
c = [ ]
it = 0
for e in b:
if e:
c.append(a[it])
it += 1
else:
c.append(d)
return cdef is_probable(a, b, min_p):
d = 0
if b[len(b)-1] == 0:
d = 1
return unresolve(embed(a, b, d)) < min_pdef get_min(a, b, min_p):
if not is_probable(a, b, min_p):
return 0
counter = 0
m = 0
d_min = 0
if b[len(b)-1] == 0:
d_min = 1
for d in range(9, d_min - 1, -1):
p = unresolve(embed(a, b, d))
if is_prime(p):
m = p
counter += 1
if counter == N:
return m
else:
return 0def min_prime(n):
min_p = 10 ** n
for m in range(n - 3, 0, -3):
pat = [ 1 ] * m + [ 0 ] * (n - m)
for q in range(10**(m-1), 10**m):
a = resolve(q)
for b in permutations(pat):
if b[0] == 0:
continue
new_min_p = get_min(a, b, min_p)
if new_min_p:
min_p = new_min_p
if min_p < 10 ** n:
return min_p
else:
return 0N = 8
for n in count(5):
m = min_prime(n)
if m:
print m
break