Project Euler+ #35 - Summing circular primes less than N
Replace the list of all numbers up to n with a dictionary of primes only

As it stands, N holds mainly False values, which are never used. It would be more idiomatic to use a dictionary, plus Python's in operator, which tells you whether a particular key exists in the dictionary. As the proportion of primes below a given number n is approximated by \$n /\mathcal{ln}(n)\$, a dictionary containing only primes as keys would be smaller than your list by a factor of about \$n/\mathcal{log}(n)\$, while look-up would be just as fast.

Your prime sieve would look like this:

def prime_sieve(n):
    '''Your docstring here.
    '''
    sieve = dict.fromkeys([i for i in range(n)])   # make a dict of all numbers up to n
    for i in range(2, ceil(sqrt(n))):
        if i in sieve:
            for j in range(i**2, n, i):
                del sieve[j]                       # remove composites from dict
    return sieve


(Note: even with this modification, the sieve still begins at size n, and takes on the order of \$\mathcal{O}(n^2)\$ operations to generate. This is a fundamental property of the Sieve of Erasosthenes. A faster implementation might forgo the sieve, generate candidate circular primes, and test them individually, e.g. using Miller-Rabin primality test.)

Follow your own pseudocode

They say in programming that good code should read like prose. Which means it should read as close to a natural sentence as possible. Writing out your program as pseudocode is a great way to prioritize readability. The pseudocode already gives you the most readable version of your code as a place to start. The task is then to rewrite it according to the syntax and idioms of the language you choose.

Based on your own pseudocode, we need:


(1) A simple way to invoke the sieve. You have that already with your prime_sieve function.


Here, your variable large should be something more descriptive. Taking cues from your pseudocode, we can call it max_rotation.

max_rotation = 10**len(str(n))
primes = prime_sieve(max_rotation)


(Note: I changed the name of the output of prime_sieve to primes, as the new dict implementation contains only primes.)


(2) A loop header that makes it clear that we are getting all rotations of each prime less than n.


Translated into Python, the second line of your pseudocode becomes:

for rotations in [get_rotations(i) for i in range(n)]:


This implies that operations such as conversion of the integer i to a string, removal of duplicates, and accumulation into a list, should all be handled by the function rotations, rather than clogging up the main body of your generate_circular_primes function.

Such a function would look like this:

def get_rotations(num)
    '''Your docstring here.
    '''
    def rotate(s, i):
        return s[i:] + s[:i]
    s = str(num)
    return set([int(rotate(s, i)) for i in range(len(s))])


(Note: using set() makes sure all rotations returned are unique.)


(3) Check if all the resulting rotations are prime.


Here, it's clearest and most idiomatic to use the all() built-in expression.

    if all(r in primes for r in rotations):



(4) And finally, we must yield only those circular primes that are less than the original n.


The final code looks like this:

from math import sqrt, ceil

def prime_sieve(n):
    '''Your docstring here.
    '''
    sieve = dict.fromkeys([i for i in range(n)])
    for i in range(2, ceil(sqrt(n))):
        if i in sieve:
            for j in range(i**2, n, i):
                if j in sieve:
                    del sieve[j]
    return sieve

def get_rotations(num):
    '''Your docstring here.
    '''
    def rotate(s, i):
        return s[i:] + s[:i]
    s = str(num)
    return set([int(rotate(s, i)) for i in range(len(s))])

def get_circular_primes(n):
    '''Your docstring here.
    '''
    circular = set()
    max_rotation = 10**len(str(n))

    primes = prime_sieve(max_rotation)
    for rotations in [get_rotations(i) for i in range(n)]:
        if all((r in primes) for r in rotations):
            circular.update(rotations)
    yield [c for c in circular if c &lt; n]


Notice that the last five lines closely match your pseudocode (with the exception of updating the set circular).



[Below is a summary of edits suggested by enedil.]



You use int() unnecessarily here:

    for i in range(2, int(ceil(sqrt(n)))):


Because ceil() already returns an integer, wrapping it in int() is redundant.



The following line can be improved to skip multiples of primes that have already been identified:

        for j in range(i*2, n, i):


As you have it, j increments through multiples of all integers between i and 2, in addition to the integers we are interested in, those greater than i. As multiples of all integers below i have already been removed from the prime list, they can be skipped in subsequent rounds. So, j should be initiated at i**2, the first composite that has not been seen before. The improved loop looks like this:

        for j in range(i**2, n, i):