プロジェクトオイラー
http://projecteuler.net/index.php
Q170.
省略
最大のものを探せ、ということなので、9876543210から探索していけばよい。頭が5以上なら2分割しかありえないことがわかる。2つに分けた数の最大公約数を得て、その約数で割る。
from itertools import permutations
import fractionsdef decode(a):
n = 0
for e in a:
n = n * 10 + e
return ndef is_prime(n):
for p in primes:
if p * p > n:
return True
elif n % p == 0:
return False
return Truedef make_primes(limit):
for n in xrange(3, limit, 2):
if is_prime(n):
primes.append(n)def gen_divisor(n):
if n == 1:
yield 1
else:
for p in primes:
if n % p == 0:
e = 1
m = n
m /= p
while m % p == 0:
e += 1
m /= p
for q in gen_divisor(m):
r = 1
for i in range(e + 1):
yield r * q
r *= p
breakdef is_pandigital2(d, a):
counter = 0
n = 0
for e in [ d ] + a:
while e:
m = e % 10
n = n | (1 << m)
e /= 10
counter += 1
return counter == 10 and n == 1023def is_pandigital(a):
if a[-1] == 0:
return False
d = 0
for e in a:
if d == 0:
d = e
else:
d = fractions.gcd(d, e)
if d == 1:
return False
for k in gen_divisor(d):
if k == 1:
continue
if is_pandigital2(k, map(lambda e: e / k, a)):
return True
return Falsedef concatenated_product(a):
if a[0] == 0:
return 0
for i in range(1, 10):
if a[i] == 0:
continue
p = decode(a[:i])
q = decode(a[i:])
if is_pandigital( (p, q) ):
return True
if a[0] >= 5:
continue
for j in range(i + 1, 10):
if a[j] == 0:
continue
q = decode(a[i:j])
r = decode(a[j:])
if is_pandigital( (p, q, r) ):
return True
if a[0] != 2:
continue
for k in range(j + 1, 10):
if a[k] == 0:
continue
r = decode(a[j:k])
s = decode(a[k:])
if is_pandigital( (p, q, r, s) ):
return True
return Falseprimes = [ 2 ]
make_primes(10 ** 5)
for a in permutations(range(9, -1, -1)):
if concatenated_product(a):
print "".join(map(str, a))
break
