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

• In python3 ceil returns an Integer so you can replace int(ceil(sqrt(n))) with ceil(sqrt(n)) if your program does not need to be backwards-compatible – ovs Feb 27 '17 at 15:43
• If you are looking for a completely different algorithm, you can have a look at my answer for a similar question : codereview.stackexchange.com/questions/58610/… . Warning: reading other solutions removes a bit of the fun. – SylvainD Feb 27 '17 at 17:16
• Also, I am the only one having trouble running the provided code ? – SylvainD Feb 28 '17 at 11:09

## 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):
'''
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.)

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)
'''
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):
'''
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):
'''
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):
'''
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):


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.

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.