- #1
- 2,168
- 193
[Project 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.
It's good up to ##\text{num} = 10^6## but then it gets slow after that. For instance it takes 16 min to solve ##10^7## case.
How can I inrease the speed of my code ?
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.
Python:
import math
import time
start = time.perf_counter()
def divisor_generator(n):
'''Generates the divisiors of input num'''
large_divisors = []
for i in range(1, int(math.sqrt(n) + 1)):
if n % i == 0:
yield i
if i*i != n:
large_divisors.append(n / i)
for divisor in reversed(large_divisors):
yield divisor
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n != 2 and n % 2 == 0:
return False
for i in range(3,int(n**(1/2))+1,2):
if n % i == 0:
return False
return True
def test_condition (divisor_array, num):
''' Testing the condition of d+n/d by taking the input as array of divisor and num'''
if len(divisor_array) %2 != 0: # the divisors of num = d3 is [1,d2,d3], and d2*d2=d3 hence d2+d3/d2 = 2d2 which is not prime
return False
if sum(divisor_array) %2 != 0: # the divisors of num = d4, [1,d2,d3,d4] (1+d4)=Prime and (d2+d3)=Prime hence sum([1,d2,d3,d4]) must be even
return False
for i in range(len(divisor_array)//2):
if is_prime(divisor_array[i] + divisor_array[-i-1]) == False:
return False
return True
Sum = 0
for num in range(2,10**6,2): #since for odd num we do not have prime numbers
divisor_list_num = list(divisor_generator(num))
if test_condition(divisor_list_num,num) == True:
Sum += numprint(Sum)
end = time.perf_counter()
print("Time : ", end-start, "sec")It's good up to ##\text{num} = 10^6## but then it gets slow after that. For instance it takes 16 min to solve ##10^7## case.
How can I inrease the speed of my code ?
