Problem #35, Circular primes below 1000000

I problem 35 är det åter igen primtal som ska itereras och undersökas:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Min ganska naiva lösning tar ca 43 sekunder på min MacBook.

#!/usr/bin/env python
from math import sqrt

max = 10**6 

def is_prime(n):
  if n == 1: return False
  if n == 2: return True
  if n & 1 == 0: return False
  for i in range(2, int(sqrt(n)) + 1):
    if n % i == 0:
      return False;
  return True;

def num_digits(n):
  d = 0
  while n > 0:
    n, d = n / 10, d + 1
  return d

def next_prime():
  n = 1
  while True:
    if is_prime(n):
      yield n
    n = n + 1

def rotate(n):
  r, n = n % 10, n / 10
  return n + r * 10 ** num_digits(n)

primes = []
for n in next_prime():
  if n > max: break
  primes.append(n)

num_circular = 0
for p in primes:
  def test_circular(n):
    for i in range(0, num_digits(n)):
      if not is_prime(n):
        return False
      n = rotate(n)
    return True 
  if test_circular(p):
    num_circular += 1

print "There are", num_circular, "primes below", max

Nej, nu är det dags för middag. Specklindad kycklingfilé med rotsaksgratäng!

Fotnot: inte späck, utan Speck!