# 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 <http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117119>`__. """ 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 else: 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): continue else: n = int (''.join (y)) if (n not in all_primes): is_circular = False break 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.