Project Euler Problem 35: counting circular primes below 1 million

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

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.

StackExchange Code Review Q#147971, answer score: 8