Project Euler & HackerRank Problem 35 Solution

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

Project Euler 35: Circular primes

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 R5 = 11111. Some of these circular-repunit primes include R19, R23, R317, R1031, R49081, 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 ≤ 106 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.