Project Euler & HackerRank Problem 35 Solution
Circular primes
by {BetaProjects} | APRIL 8, 2009 | Project Euler & HackerRankProject 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 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.