Euler 035 - counting circular primes

How many circular primes (primes that when rotated are still primes) are there below one million?

See Problem 20.

Again, this rescues a lot of code from previous problems, but the solution is less than perfect. The Euler guidelines say that every problem should be computable within a minute, but despite much tweaking, this solution takes significantly longer.

For speed, primes should be generated only once, for which we use a classic sieve:

def iter_primes (n):
   After `Tim Hochberg <>`__.
   yield 2
   D = {}
   q = 3
   while (q <= n):
      p = D.pop (q, 0)
      if p:
         x = q + p
         while x in D:
            x += p
            D[x] = p
         yield q
      D[q*q] = 2*q
      q += 2

We then accumulate all the primes below a million (which takes only a few seconds):

all_primes = []
for x in iter_primes (1000000):
   all_primes.append (x)

And then check every prime. Each prime is rotated and checked to see if it is in the list of primes:

circ_primes = []
for x in all_primes:
   pstr = str (x)
   is_circular = True
   for y in iter_rotate_seq (pstr):
      if (y == pstr):
   n = int (''.join (y))
   if (n not in all_primes):
      is_circular = False
   if (is_circular):
      print x
      circ_primes.append (x)
      print "Length:", len (circ_primes)

iter_rotate_seq is a simple function that produces every rotation of a sequence. Note that the first rotation is a move of 0, giving the original sequence:

def iter_rotate_seq (seq):
   for i in range (len (seq)):
      yield seq[i:] + seq[:i]

The answer is 55. Computation time is 261.6 seconds.