11
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You should learn to use a profiler on your code. Python even comes with a couple. \$\endgroup\$ – Peilonrayz Nov 24 '16 at 10:00
  • \$\begingroup\$ while numbers: p = numbers.pop() prime_list.append(p) that does not work. sets are not sorted. If it works, it is by chance. \$\endgroup\$ – njzk2 Nov 24 '16 at 21:05
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yeah it worked !!! I have changed my list to set and gave me output for 100,000 limit in 60 ms and for 1 million limit in 1.2 second \$\endgroup\$ – Unique Nov 24 '16 at 9:45
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like the 'think before code' approach. There are real improvements therein! Further to your prime check, it only needs to check as far as n/2 digits - an approximation for root(N) limit check. \$\endgroup\$ – Philip Oakley Nov 24 '16 at 19:50
  • \$\begingroup\$ @PhilipOakley regarding the prime check, that's exactly what I meant by saying you only need all the primes below 1000 instead of 1,000,000 because sqrt(1e6) = 1000. I think it's unnecessary to recompute the primes for each power of 10: computing all those 168 numbers once at the start of the program is good enough because you need to go to the 6th digits numbers anyways. \$\endgroup\$ – Olivier Grégoire Nov 24 '16 at 21:51
  • 1
    \$\begingroup\$ You can also assume that the first digit is the smallest digit, leaving only 1799 numbers to check. \$\endgroup\$ – user123970 Nov 24 '16 at 22:08
  • 1
    \$\begingroup\$ "1793" seems really "à propos" here :P \$\endgroup\$ – Olivier Grégoire Nov 24 '16 at 22:14
  • \$\begingroup\$ Better yet; if furthermore you leave out the numbers consisting of only 7's and 9's (which are never prime for nice reasons of modular arithmetic), you're left with precisely 1729 numbers ;) \$\endgroup\$ – user123970 Nov 24 '16 at 22:22
7
\$\begingroup\$

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())
\$\endgroup\$
  • \$\begingroup\$ Re "I am not quite sure how your prime generation algorithm is supposed to work", I think it's meant to also be a sieve of Erastophenes, but (as I mentioned in my answer) I think it relies on set iterating in increasing order, which would make it buggy. \$\endgroup\$ – Peter Taylor Nov 25 '16 at 9:21
  • \$\begingroup\$ Indeed, now that I look at it, it does seem to be an implementation of the sieve. When I tried, my implementation looked faster but I am not sure that this behavior is consistent depending on the input... \$\endgroup\$ – SylvainD Nov 25 '16 at 14:21
2
\$\begingroup\$

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.

\$\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.