Count prime numbers whose rotations are all prime

Question

This code solves Project Euler problem 35:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. How many circular primes are there below one million?

from collections import deque

def sieve(limit):
    nums = [True] * (limit+1)
    nums[0] = nums[1] = False

    for i, is_prime in enumerate(nums):
        if is_prime:
            yield i
            for n in range(i*i, limit+1, i):
                nums[n] = False

def rotations(n):
    l = deque(list(str(n)))
    r = []

    for _ in range(len(l)):
        r.append(int("".join(list(l))))
        l.rotate()
    return r

def circular_prime(n):
    cp = []
    s = list(sieve(n))
    for i in s:
        r = rotations(i)
        flags = [False] * len(r)
        for k, j in enumerate(r):
            if j in s:
                flags[k] = True
        if all(flags):
            print(i)
            cp.append(i)
    return len(cp)


print(circular_prime(1000000))

How can I speed it up? It takes too long if I run it with standard Python interpreter. However, I am able to reduce execution time to 13 seconds by running in "pypy" interpreter.

Answer 1

Don't check if there are even digits

Add

if n<10:
    return [n]
if any(even in str(n) for even in "02468"):
    return []

into rotations, because every number (except for 2) with the last even digit will not be prime, there's no sense in generating rotations for those.

Avoid excessive conversions

l = deque(str(n)) - no list conversion needed Also check string slices - you can do rotations just with them, not the deque.

Avoid changing the collection while you're iterating over it

for i, is_prime in enumerate(nums):
    ...
            nums[n] = False

is bad. Refactor it - maybe into while loop.

Use list comprehensions

flags variable is clearly a mess. Let's see...

    flags = [False] * len(r)
    for k, j in enumerate(r):
        flags[k] = j in s #True for True, False for False
    if all(flags):

Ok, now move it into the initialization of flags.

    flags = [j in s for k,j in enumerate(r)]
    if all(flags):

k is not needed. And flags too:

    if all(j in s for j in r):

This looks better and works faster - because it stops after the first False. But now we don't need r:

    if all(j in s for j in rotations(i)):

And now you can rewrite rotations to use yield instead of creating the list. This will be much faster.

Don't transform the sieve into the list

You spend time and memory for nothing. Work with the sieve, not with the list. Searching in the sieve will be \$O(1)\$, not \$O(n)\$ (if s[j] instead of if j in s). The for i loop now will be over the whole range (2..n), skipping if not s[i].

Answer 2

Disclaimer: This review will mention improvements to your code that have probably been provided by other answers. At the end, I will suggest a completely different algorithm to solve this problem.

Better usage of the sieve

Using a sieve is a good idea especially because we have a known upper-bound for the values we are interested in. However, the conversion from the sieve into a list makes it slower to use: it makes all other prime checks expensive as one need to perform a linear search in the list. A much faster alternative is to use it as is: an array mapping number to their primality.

In practice, you just need to return nums from the sieve function and then:

def circular_prime(n):
    cp = []
    s = sieve(n)
    for i, is_prime in enumerate(s):
        if is_prime:
            r = rotations(i)
            flags = [False] * len(r)
            for k, j in enumerate(r):
                if s[j]:
                    flags[k] = True
            if all(flags):
                print(i)
                cp.append(i)
    return len(cp)

This simple change leads to a huge performance improvement.

Flags

The logic involving flags can be simplified a lot and be: if all(s[j] for j in rotations(i)):.

Perform a smaller number of prime test

For every circular number found, we check all its rotations. Eventually, all numbers have been checked many times. A different strategy could be to check whether the number we are considering is the smallest among its rotations. If it is and if it is indeed a circular primes, all its rotations can be added to the result at once.

            r = set(rotations(i))
            if i == min(r) and all(s[j] for j in r):
                print(r)
                cp.extend(r)

A different algorithm

A few mathematical observations can be performed for the number (bigger than 9) we are looking for:

• primes numbers (bigger than 9) will not end in 0, 2, 4, 6, 8 or 5. This leads to a last digit being 1, 3, 7, 9.

• thus, circular primes will not contain any of these numbers because they would correspond to the last digit of a rotation. Circular primes are only permutations of 1, 3, 7 and 9.

We can limit the search space by looking for these permutations: when considering numbers with n digits, you'll only consider 4ⁿ numbers instead of 10ⁿ (when n = 6 for instance, it makes the difference between 4096 and 100000).

We get something like:

def circular_prime(nb_dig_max):
    cp = [2, 3, 5, 7]
    final_numbers = {'1', '3', '7', '9'}
    s = sieve(10 ** nb_dig_max)
    for l in range(2, nb_dig_max + 1):
        for p in itertools.product(final_numbers, repeat=l):
            p_int = int(''.join(p))
            perm = set(rotations(p_int))
            if p_int == min(perm) and all(s[n] for n in perm):
                cp.extend(perm)
    return len(cp)

At this stage, we've limited the number of prime checks to such a small number that using a sieve leads to performance no better than a simple prime check function:

def is_prime(n):
    """Checks if a number is prime."""
    if n < 2:
        return False
    return all(n % i for i in range(2, int(math.sqrt(n)) + 1))


def circular_prime(nb_dig_max):
    cp = [2, 3, 5, 7]
    final_numbers = {'1', '3', '7', '9'}
    for l in range(2, nb_dig_max + 1):
        for p in itertools.product(final_numbers, repeat=l):
            p_int = int(''.join(p))
            perm = set(rotations(p_int))
            if p_int == min(perm) and all(is_prime(n) for n in perm):
                cp.extend(perm)
    return len(cp)

Answer 3

Consider the circular primes 197, 719, 971 given as an example. When 197 is reached, the current code checks the two rotations 719 and 971 to see if they are prime. Then when 719 is reached, 971 and 197 are tested. But we already know that the three numbers are circular primes from the first time they were tested. So the code is doing 6 rotations and checks when only the first two are needed. For a 6-digit circular prime that would be 30 rotations instead of only 5.

Here's some code (untested) to show the idea.

def count_circular_primes(n):
    count = 0
    primes = list(sieve(n))

    for prime in primes:
        r = rotations(prime)

        # if they are circular primes, count them
        if all(primes[i] for i in r):
            count += len(r)

        # mark all the rotations as done
        for i in r:
            primes[i] = False

    return count