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 < 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

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 < 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 no

StackExchange Code Review Q#156395, answer score: 6