Euler Problem 357

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.



In [1]:

    
import primesieve
import numpy as np

N = 10**8
M = int(N**0.5)

arr = np.zeros((N + 1), dtype=bool)

primes = set(primesieve.primes(N+1))

for d in range(1, M + 1):
    for e in range(d, N // d + 1):
        if (d + e) not in primes:
            arr[d * e] = 1

print(sum(n for n in range(N + 1) if arr[n] == 0))









    



1739023853137

Note: This program runs for over nine minutes on my machine, so I should probably find a more efficient algorithm.



In [ ]: