42 lines
742 B
Python
42 lines
742 B
Python
#!/usr/bin/env python3
|
|
|
|
def primes(n):
|
|
sieve = [False]*n
|
|
for p in range(2, int(n**0.5)):
|
|
if sieve[p]:
|
|
continue
|
|
for i in range(p**2, n, p):
|
|
sieve[i] = True
|
|
return [p for p, t in enumerate(sieve) if not t][2:]
|
|
|
|
def solve(p1, p2, k):
|
|
t = extended_euclid(p2, k)
|
|
return ((t * p1) % k) * p2
|
|
|
|
def extended_euclid(p2, k):
|
|
a = k
|
|
b = p2
|
|
t1, t2 = 0, 1
|
|
while b != 0:
|
|
k = a // b
|
|
a, b = b, a % b
|
|
t1, t2 = t2, t1 - k*t2
|
|
return t1
|
|
|
|
|
|
n = 10**6
|
|
|
|
|
|
nums = primes(n + 1000)
|
|
nums = [nums[i] for i in range(1, len(nums)) if nums[i-1] <= n]
|
|
|
|
k = 10
|
|
s = 0
|
|
|
|
for p1, p2 in zip(nums[1:], nums[2:]):
|
|
if p1 > k:
|
|
k *= 10
|
|
s += solve(p1, p2, k)
|
|
|
|
print(s)
|