8
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – ovs Feb 27 '17 at 15:43
  • \$\begingroup\$ 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. \$\endgroup\$ – SylvainD Feb 27 '17 at 17:16
  • \$\begingroup\$ Also, I am the only one having trouble running the provided code ? \$\endgroup\$ – SylvainD Feb 28 '17 at 11:09
6
\$\begingroup\$

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):
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.