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

Question

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

Answer 1

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 not been seen before. The improved loop looks like this:

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

Answer 2

There are some things you can do to improve overall readability:

• the comments that you have before the functions should be the regular Python docstrings
• the N variable in the prime_sieve() is not the best choice - first of all, the upper-case should be used for constant things (PEP8 reference) and, N is meaningless, how about calling it sieve?
• you can shorten the initial sieve element definition to sieve[0] = sieve[1] = False
• don't forget about the proper use of white spaces in expressions

Here are the first two functions applying the suggested changes:

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


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

---

Now, let's see what we can do about the generate_circular_primes_less_than function.

First of all, the function is not easily understandable and is really missing a helpful docstring and meaningful comments explaining the way it works.

Also, you can decrease the nestedness by negating the first condition and using continie statement:

for num in range(n):
    if not is_prime[num]:
        continue

    s = str(num)
    # ...

I would also define the circular_primes as a separate variable, replacing:

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

with:

circular_primes = (r for r in rotations if r < n and is_prime[r])
for circular_prime in circular_primes:
    is_prime[circular_prime] = False  # remove duplicates (like 11)
    yield circular_prime

The reduce() part can also benefit from defining with a readable variable name, e.g.:

check_circular_primes = reduce(lambda y, x: y and is_prime[x], rotations, True)
if check_circular_primes:
    # ...

FYI, this is commonly known as "Extract Variable" refactoring technique.

Answer 3

I may not be an expert on code readability or that special given problem, but my suggestion would be to generally shorten the amount of text in your code.

Maybe generate_circular_primes_less_than was better to read if you wrote something like:

#generate circular primes less than var
def circPrimes(n):
    [ ... ]

I don't know if that helps you at all, but having less characters on the screen would always help to optimize readability, and I personally think a function name should be short and straight forward, description should be comments.