41 lines
799 B
Python
41 lines
799 B
Python
# Consider the divisors of 30: 1,2,3,5,6,10,15,30.
|
|
# It can be seen that for every divisor d of 30, d+30/d is prime.
|
|
#
|
|
# Find the sum of all positive integers n not exceeding 100 000 000
|
|
# such that for every divisor d of n, d+n/d is prime.
|
|
|
|
from math import floor, sqrt
|
|
|
|
from projecteuler import sieve, timing
|
|
|
|
|
|
N = 100000000
|
|
primes = sieve(N + 2)
|
|
|
|
|
|
def check_d_nd_prime(n):
|
|
limit = floor(sqrt(n))
|
|
|
|
for i in range(2, limit + 1):
|
|
if n % i == 0:
|
|
if not primes[i + int(n/i)]:
|
|
return False
|
|
|
|
return True
|
|
|
|
|
|
@timing
|
|
def p357():
|
|
sum_ = 1
|
|
|
|
for i in range(2, N + 1, 2):
|
|
if primes[i + 1] and check_d_nd_prime(i):
|
|
sum_ += i
|
|
|
|
print('Project Euler, Problem 357')
|
|
print(f'Answer: {sum_}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p357()
|