Project Euler 357 prime number generator in Python 3 I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks:


  Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, d+n/d is prime.


The code is this: 

#!/bin/env python3

import time 
import math

"""
https://projecteuler.net/problem=357

"""

start = time.time()


def primes(ubound=10**5):
    """ Generating prime numbers LIST
        https://stackoverflow.com/a/8627193/1770460
    """
    size = (ubound - 3) // 2
    a = [False] * size
    s = 0
    primes = []
    while s &lt; size:
        t = 2 * s
        p = t + 3
        primes.append(p)
        for n in range(t * (s + 3) + 3, size, p):
            a[n] = True
        s = s + 1
        while s &lt; size and a[s]:
            s = s + 1
    return primes

the_primes = primes()

def number_divisors(max_limit=10**5):
    """ Find the divisors of every number.
        Return it in a dict in the format: 
        { number1: [divisor1, divisor2 ... ], .. }
    """
    num_divs = {}
    for i in range(4, max_limit): 
        if i in the_primes:
            continue
        else:
            sq = math.sqrt(i)
            for n in range(2, int(sq) + 1):
                if i not in num_divs:
                    num_divs[i] = [1]
                if i % n == 0:
                    if n == i / n:
                        num_divs[i].append(n)
                    else:
                        num_divs[i].extend((n, i / n))
    return num_divs



def find_count(d):
    """ Check every number whether the divisors i.e. d + number / d is 
        prime. 
    """
    assert d is not None

    count = 0
    for number, list_divisors in d.items():
        all_primes = True
        for each_div in list_divisors:
            val = (each_div + (number / each_div))
            if val not in the_primes:
                all_primes = False
                break
        if all_primes:
            count += 1 
    return count




if __name__ == '__main__':

    num_divisors = number_divisors()
    print(find_count(num_divisors))

    elapsed_time = (time.time() - start)
    print('time elapsed %s sec.' % elapsed_time)


Profiling the script shows that the find_count is the first bottleneck and by advice of other answers the values should be cached(?) somehow.



$ python3 -m cProfile 357.py                                      
275
time elapsed 167.41558241844177 sec.
         583580 function calls in 167.416 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  167.416  167.416 357.py:3(&lt;module&gt;)
        1    0.020    0.020    0.020    0.020 357.py:30(primes)
        1   24.526   24.526   24.740   24.740 357.py:51(number_divisors)
        1  142.655  142.655  142.655  142.655 357.py:75(find_count)


Any advice on how to improve find_count()?
The most obvious improvement is to notice that if i in the_primes and if val not in the_primes both take \$\mathcal{O}(n)\$ time. If you made the_primes a set instead of a list it would only be \$\mathcal{O}(1)\$. So just write:

the_primes = set(primes())


Also note that your "prime number generator" is not actually a Python generator. For that you would need to add a yield:

def primes(ubound=10**5):
    """ Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
    size = (ubound - 3) // 2
    a = [False] * size
    s = 0
    while s &lt; size:
        t = 2 * s
        p = t + 3
        yield p
        for n in range(t * (s + 3) + 3, size, p):
            a[n] = True
        s = s + 1
        while s &lt; size and a[s]:
            s = s + 1


The set() call will then consume the generator. This will not make your code run faster, though (it needs about the same CPU) It might save you some memory, because you don't need the conversion from the internal list to the external set.



Your original code takes about 43.5s on my machine. With the two changes in this post this drops down to less than 1.7s:

$ python3 -m cProfile 357.py
275
time elapsed 1.6228196620941162 sec.
         583585 function calls in 1.623 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   ...
     9592    0.011    0.000    0.011    0.000 euler_357.py:14(primes)
        1    0.001    0.001    1.623    1.623 euler_357.py:3(&lt;module&gt;)
        1    1.524    1.524    1.584    1.584 euler_357.py:34(number_divisors)
        1    0.026    0.026    0.026    0.026 euler_357.py:56(find_count)
   ...