# 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.