Project Euler+ #35 - Summing circular primes less than N Overview

The following code is a solution for a Project Euler+ problem on Hackerrank. A circular prime is a prime number whose rotations are also prime. For example, 197 is a circular prime since it and all it's rotations (197, 971, 719) are prime.

The sum of all circular primes less than 100 is:

sum(2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97) = 446 


Code Redability

After learning about list comprehensions in python, I'm concerned that my code readability may have taken a nosedive. I'd like to make my code as understandable as possible so that someone reading it could quickly deduce the strategy I used to solve the problem.

I'm mostly concerned with my generate_circular_primes_less_than function as it goes 5 nested blocks deep and seems to be more confusing than it could be.



Here's the code for my solution:

from math import sqrt, ceil
from functools import reduce

# generates a list of n booleans where indexes correspond to primality
def prime_sieve(n):
    N = [True] * n
    N[0] = False
    N[1] = False
    for i in range(2, int(ceil(sqrt(n)))):
        if N[i]:
            for j in range(i*2, n, i):
                N[j] = False
    return N

# rotates the first i chars of a string to the end
def rotate(s, i):
    return s[i:] + s[:i]

def generate_circular_primes_less_than(n):
    large = 10**len(str(n))
    is_prime = prime_sieve(large)

    for num in range(n):
        if is_prime[num]:
            s = str(num)

            rotations = [int(rotate(s, i)) for i in range(len(s))]

            if reduce(lambda y, x: y and is_prime[x], rotations, True):
                for circular_prime in (r for r in rotations if r &lt; n and is_prime[r]):
                    is_prime[circular_prime] = False # remove duplicates (like 11)
                    yield circular_prime
            else:
                for r in rotations:
                    is_prime[r] = False # no need to recheck non-circular primes

#
# MAIN
if __name__ == "__main__":
    n = int(input())
    print(sum(generate_all_circular_primes_less_than(n)))




However, the pseudocode I wrote when designing my solution is much simpler:


1. sieve all primes less than the maximum rotation value
2. get the rotations for each prime less than n
     if all rotations are prime:
       add the rotations less than n to the sum





Sometimes it seams that adding comments only masks unintuitive code (like putting lipstick on a pig). What would you suggest to improve the readability?
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):