42 lines
916 B
Python
42 lines
916 B
Python
def primes_sieve(nmax):
|
|
a = [0 for _ in range(nmax)]
|
|
for i in range(2, nmax):
|
|
if a[i] == 0:
|
|
for j in range(i + i, nmax, i):
|
|
a[j] = i
|
|
return a
|
|
|
|
|
|
def is_number(n, primes):
|
|
f = n // 2
|
|
if primes[f] == 0:
|
|
for d in [2, f]:
|
|
if primes[d + n // d] != 0:
|
|
return False
|
|
return True
|
|
|
|
for d in range(1, n // 2 + 1):
|
|
if n % d == 0:
|
|
if primes[d + n // d] != 0:
|
|
return False
|
|
if d * d > n:
|
|
break
|
|
return True
|
|
|
|
|
|
def euler_357():
|
|
r = 1 # n = 1 is a number
|
|
ps = primes_sieve(100_000_000)
|
|
for p in range(3, len(ps)):
|
|
if ps[p] == 0:
|
|
n = p - 1
|
|
if is_number(n, ps):
|
|
r += n
|
|
return r
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_357()
|
|
print("e357.py: " + str(solution))
|
|
assert solution == 1739023853137
|