## Project Euler & HackerRank Problem 35 Solution

##### Circular primes

by {BetaProjects} | APRIL 8, 2009 | Project Euler & HackerRank### Project Euler Problem 35 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

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 only circular primes are repunits.

Repunits are numbers composed of only 1s, and is described as R_{5} = 11111. Some of these circular-repunit primes include R_{19}, R_{23}, R_{317}, R_{1031}, R_{49081}, and on from there.

To solve this problem we generate a set of 78,498 prime numbers below 1 million using our `prime_sieve()`

function. We remove all primes greater than five that contains any {0, 2, 4, 5, 6 or 8} which would make it non-prime during a rotation. That leaves only 1,113 prime candidates to investigate. They are added to the set `primes`

along with 2 and 5.

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

The set `primes`

is also used to check numbers for primality. If a number exists in the set then it‘s prime, and if not, it‘s composite.

The `all()`

function returns `True`

if __ all__ the rotations are a member of the

`primes`

set. This would make `p`

a circular prime number and it‘s added to the list. `circular_primes = [int(p) for p in primes if all(pr in primes for pr in rotate(p))]`

#### HackerRank version

HackerRank Project Euler 35 wants us to find the sum of the circular primes below 10 ≤ N ≤ 10^{6} instead of a count. The same algorithm solves both requirements. The program listed here prints the count, the circular primes and their sum.

### Python Source Code

### Last Word

Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A068652: Numbers such that every cyclic permutation is a prime.