(18 votes, average: 4.78 out of 5)

## 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 R11 = 11111111111) with many digits. The only circular primes after one million are repunit primes: R19, R23, R317, R1031, R49081, 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.

This program and method
solves all test cases for
Project Euler 35 on HackerRank

#### 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.

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.
|55|

#### Afterthoughts

Project Euler 35 Solution last updated

## Discussion

### 3 Responses to “Project Euler 35 Solution”

```from Euler import prime_sieve, is_prime

def circular (n):
circ = []
n = str(n)
for i in range(len(n)):
circ.append(int(n[1:]+n[0]))
n = n[1:]+n[0]
return circ

def is_prime_list (List):
for i in List:
if not is_prime(i):
return False
return True

primes = prime_sieve(1000000)
circ = []
for i in primes:
if (is_prime_list(circular(i))):
circ.append(i)

print "Answer to PE35 = " + str(len(circ))
```

Posted by Murilo Camargos | January 27, 2013, 2:53 PM
2. Great explanation! Thank you.

Posted by Tarren | April 9, 2009, 3:36 AM