## Project Euler 35: Find the number of circular primes below one million

#### Project Euler 35 Problem Description

Project Euler 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?

#### Analysis

While researching circular primes, not to be confused with permutable primes, it became clear that the only interesting ones are below one million. After one million the circular primes are only repunits (a number composed of just 1s, such as R_{11} = 11111111111) with many digits. The only circular primes after one million are repunit primes: R_{19}, R_{23}, R_{317}, R_{1031}, R_{49081}, and on from there.

To solve this problem we generate a set of prime numbers below 1 million (78,498 primes) using our prime sieve and excluded those that contained the digits {0, 2, 4, 5, 6 or 8} (except primes 2 and 5) because as the prime is rotated it cannot end with any of these digits and still remain prime. That leaves 1,113 prime candidates to investigate.

We have a variable `s`

predefined as a set {0,2,4,5,6,8} so we can check the intersection with the stringified version of the prime number candidate. If there is no intersection the prime is added to the set `primes`

.

primes = set(['2','5']+[str(p) for p in prime_sieve(L) if not set(str(p)).intersection(s)])

The set `primes`

also serves as a de facto ‘is prime()’ function. If a particular element exists in the set then the number is prime and if it does not, then it’s composite.

As we consider each qualified prime, the `all()`

function returns `True`

if all the rotations are a member of the `primes`

set and, therefore, a circular prime number.

circular_primes = [p for p in primes if all(pr in primes for pr in rotate(p))]

This solution handles the HackerRank Project Euler 35 problem as well. In fact, we collect circular prime values as HackerRank requests a sum of circular primes below some limit less than one million and Project Euler only requires a count.

#### Project Euler 35 Solution

Runs < 0.125 seconds in Python 2.7.Use this link to get the Project Euler 35 Solution Python 2.7 source.

#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### Afterthoughts

- Function
`prime_sieve`

is listed in Common Functions and Routines for Project Euler - Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A016114: Circular primes (numbers which remain prime under cyclic shifts of digits).

*Project Euler 35 Solution last updated*

About 4s in python:

Thanks for the comment. I reformatted your code.

Great explanation! Thank you.