# Problem 35

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?

``````

In [13]:

import math

``````
``````

In [47]:

def primes_upto(n):
if n < 2:
return
marked = [0] * (n+1);
value = 3
yield 2
while value <= n:
if marked[value] == 0:
yield value
i = value
while i <= n:
marked[i] = 1
i += value
value += 2

def primes_under(n):
return primes_upto(n-1)

def num_digits(n):
if n < 0:
return num_digits(-n)
if n < 10:
return 1
return 1 + num_digits(n//10)

def rotate(n):
right = n % 10
left = n // 10
for _ in range(num_digits(n) - 1):
right *= 10
return right + left

def rotations(n):
yield n
x = rotate(n)
while x != n:
yield x
x = rotate(x)

def is_circular_prime(n, P):
"""
@param n Prime number to test.
@param P Set of known primes.
"""
for i in rotations(n):
if i not in P:
return False
return True

def circular_primes(P):
for i in P:
if is_circular_prime(i, P):
yield i

``````
``````

In [50]:

P = set(primes_under(1000000))
C = set(circular_primes(P))
print("Number of circular primes under 1000000 is:", len(C))

``````
``````

Number of circular primes under 1000000 is: 55

``````
``````

In [ ]:

``````