# Project Euler Problem 35: Circular Primes¶

The source code for this problem can be found here.

## Problem Statement¶

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?

## Solution Discussion¶

Simply iterate over the primes below one million and count how many satisfy the conditions for a circular prime.

## Solution Implementation¶

from typing import Iterator

from lib.digital import num_digits
from lib.sequence import Primes

def rotated(p: int) -> Iterator[int]:
""" Generate all rotations of the decimal digits of p

:param p: the initial value of p
:return: a generator of all decimal digit rotations of p
"""

def rotl(x: int, n: int) -> int:
""" Helper function to rotate the decimal digits of x left by one position

:param x: the integer to rotate
:param n: the number of decimal digits in x
:return: x left rotated by one digit
"""

return ((x * 10) + int(x // (10 ** (n - 1)))) % (10 ** n)

n_digits = num_digits(p, base=10)
q = rotl(p, n_digits)
while q != p:
yield q
q = rotl(q, n_digits)

def solve():
""" Compute the answer to Project Euler's problem #35 """

upper_bound = 1000000

# Get all primes lower than one million, build a set to make membership tests cheap, i.e. O(1)
primes = set(Primes(upper_bound=upper_bound))

# Iterate over the primes, checking for those that are circular
for prime in primes:
for q in rotated(prime):
if q not in primes:
break
else:


solutions.problem35.rotated(p)
Parameters: p (int) – the initial value of p Iterator[int] a generator of all decimal digit rotations of p
solutions.problem35.solve()