プロジェクトオイラー
http://projecteuler.net/index.php
Q134.
素数p1とその次の素数p2に対して、p1をお尻にした数でp2で割り切れるものが、p1が5以上で必ずある。例えば、p1=19,p2=23なら、1219が23で割り切れる。p1が5から100万までについてのその最小の数の総和
上の例なら、
100n + 19 ≡ 0(mod 23)
を解けばいいから、要するにユークリッドの互除法。
def gen_primes():
yield 2
yield 3
n = 3
while True:
n += 2
p = 3
while True:
if p * p > n:
yield n
break
if n % p == 0:
break
p += 2def euclid(a, b):
x1 = 1
y1 = 0
x2 = 0
y2 = 1
count = 0
while b > 1:
count += 1
m = a % b
d = a / b
a, b = b, m
x1, y1 = x1 * d + y1, x1
x2, y2 = x2 * d + y2, x2
if count & 1:
return (x2, -x1)
else:
return (-x2, x1)def ten_pow(n):
m = 10
while n >= m:
m *= 10
return mdef S(p1, p2):
tp = ten_pow(p1)
t = euclid(tp, p2)
return (p2 - (p1 * t[0] % p2)) * tp + p1N = 10 ** 6
s = 0
p1 = 5
for p2 in gen_primes():
if p2 < 7:
continue
elif p1 > N:
break
s += S(p1, p2)
p1 = p2
print s
