Project Euler 357 - Prime Generating Integers

Official link: https://projecteuler.net/problem=357

Thought Process

I had to re-write my code for this problem 3 times to get into the time limit boundary, 1st try took me ~2,500s (almost 40 mins), 1st try took ~700s and finally 3rd iteration took ~50 seconds, so this problem was really all about finding a highly efficient algorithm, let's start with the mathematics first

Now for the algorithm:

  1. Generate a list, primelist, where primelist[x] = True if x is a prime and False if x is not a prime.

    • The reason this is much faster than actually finding all the primes or using an is_prime function is because the main bulk of our computation is checking whether or not a number is prime, accessing an list takes only O(1) time.

  2. Generate a list called values which has all numbers, n, from 2 to 100,000,000 such that n = 4k + 2, because of math fact 2

  3. Loop through the list values using the variable x, and I do a preliminary test and check if x+1 is prime, because of math fact 1

  4. If this is true I continue and do a modified Divisors function that checks if all d + n/d are prime where d are divisors of n, this process stops immediately if it encounters a case where it is not prime.

  5. If it passes both of these test then we add x to a sum

My prime generator and Divisor function are on my Essential Functions page!

Interactive Code

Enter an integer (yourinput)

Code will output the sum of all positive integers n not exceeding yourinput such that for every divisor d of n, d+n/d is prime