Project Euler Problem 35: counting circular primes below 1 million

Question

Project Euler Problem 35 asks:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

How many circular primes are there below one million?

import itertools
import math
import time

prime_list = []
#num = 14
count = 0
limit = 100000
time.clock()

def get_primes(n):
    numbers = set(range(n, 1, -1))
    #primes = []
    while numbers:
        p = numbers.pop()
        prime_list.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    #return primes

get_primes(limit)

print "Done", time.clock()

for r in xrange(2,limit):
    #b = 1
    if r in prime_list:
        #print r,count
        num = str(r)
        if (all(int(num[i:]+num[:i]) in prime_list for i in xrange(len(num)))):
            count += 1
print count,time.clock()

I am generating all possible primes with another function and it is giving me output in 60-80 ms for limit=1000000

Still the loop is taking around 19 seconds for finding cicular prime count under limit=100000

Answer 1

For prime_list you want a fast test for in prime_list: that's what set is for. Using a list gives linear time tests, whereas a set should be near-constant time.

On the other hand, set doesn't guarantee the iteration order, so I think that get_primes is probably buggy.

Answer 2

Regarding the primes above 10. If they're prime and all of their rotations must be primes, then each digit must be in the set of 1, 3, 7 and 9. So for all 2 digits numbers,\$ 4^2 \$, for all 3 digits, \$ 4^3 \$, until 6. That's exactly 5456 numbers to check, which is very few, compared to 1 million. Now we have all the numbers possible and only those.

Also, you play with numbers with a max value of 1 million. You also only need to check if a number is prime. To do that, you only need to generate primes until 1000 and check if one of the candidates is divisible by any of those prime numbers. There are 168 primes under 1000. So you can store them in an array. It's faster than always generating the primes again and again.

This should already improve your timing by a really large factor.

Answer 3

Split your code into smaller, reusable, testable, documented parts

You could re-organise your code to make it clearer, easier to test and thus easier to improve by writing small functions with a clear purpose, with a proper return value (instead of relying on global variable).

import time

def get_primes(n):
    """Get list of prime number from 2 to n included."""
    prime_list = []
    numbers = set(range(n, 1, -1))
    while numbers:
        p = numbers.pop()
        prime_list.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return prime_list

def euler35(limit = 100000):
    count = 0
    prime_list = get_primes(limit)
    for r in xrange(2,limit):
        if r in prime_list:
            num = str(r)
            if (all(int(num[i:]+num[:i]) in prime_list for i in xrange(len(num)))):
                count += 1
    return count

def test_get_primes():
    assert get_primes(1) == []
    assert get_primes(2) == [2]
    assert get_primes(7) == [2, 3, 5, 7]
    assert get_primes(8) == [2, 3, 5, 7]
    assert get_primes(9) == [2, 3, 5, 7]
    assert get_primes(10) == [2, 3, 5, 7]
    assert get_primes(11) == [2, 3, 5, 7, 11]

def test_euler35():
    assert euler35(100) == 13
    assert euler35() == 43

test_get_primes()

time.clock()
test_euler35()
print(time.clock())

Optimisation : using the right data structure for the right task

As mentionned in the other answer, using a set instead of a list should lead to clear performance improvements.

You just need to update :

prime_list = get_primes(limit)

into:

prime_set = set(get_primes(limit))

Simplify your code

You could get rid of if r in prime_set by iterating directly prime_set. Also you can get rid of superfluous parenthesis:

def euler35(limit = 100000):
    count = 0
    prime_set = set(get_primes(limit))
    for r in prime_set:
        num = str(r)
        if all(int(num[i:]+num[:i]) in prime_set for i in xrange(len(num))):
            count += 1
    return count

Different prime generation algorithm

I am not quite sure how your prime generation algorithm is supposed to work but a simple implementation of the Eratosthenes algorithm proves to be slightly faster (at least on my machine).

This is the nice benefit of having split your code into small meaningful part is that you can easily change the underlying implementation.

def sieve(lim):
    """Computes the sieve of Eratosthenes for values up to lim included."""
    primes = [True] * (lim + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(math.sqrt(lim)) + 1):
        if primes[i]:
            for j in range(i * i, lim + 1, i):
                primes[j] = False
    return primes

def primes_up_to(lim):
    """Uses a sieve to return primes up to lim included."""
    return (i for i, p in enumerate(sieve(lim)) if p)

def euler35(limit = 1000000):
    count = 0
    prime_set = set(primes_up_to(limit))
    for r in prime_set:
        num = str(r)
        perms = [int(num[i:]+num[:i]) for i in xrange(len(num))]
        if all(p in prime_set for p in perms):
            count += 1
    return count

Different strategy

Usually Project Euler is more than just implementing the straight forward solution : it could be a good idea to find a solution that would work for even bigger search spaces. You'll find such a strategy in this other code review.

Here is the code I had written (the argument works slightly differently but you'll get the spirit) and the corresponding unit tests you could use to check that my code runs ~10 times faster:

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 euler35_bis(nb_dig_max=6):
    # permutations of 2 digits or more must contain only 1, 3, 7, 9
    count = 4  # counting 2, 3, 5 and 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 = {int(''.join(p[i:] + p[:i])) for i in range(len(p))}
            if p_int == min(perm) and all(is_prime(n) for n in perm):
                count += len(perm)
    return count

def test_euler35():
    assert euler35(100) == 13
    assert euler35(100000) == 43
    assert euler35() == 55

def test_euler35_bis():
    assert euler35_bis(2) == 13
    assert euler35_bis(5) == 43
    assert euler35_bis() == 55

test_get_primes()

time.clock()
test_euler35()
# test_euler35_bis()
print(time.clock())

Answer 4

You should write a is_even(N) function to check if there in any even digit (0,2,4,6,8) anywhere in the digits of the main number. If there is, return False, do not even bother to rotate because at some point that even number will come at the end and make the number not circular prime.

This should reduce the checking burden significantly.