035 - counting circular primes

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.