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.
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.
Afterthoughts
- Function
prime_sieveis 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).
About 4s in python:
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 PMThanks for the comment. I reformatted your code.
Posted by Mike | January 29, 2013, 4:02 PMGreat explanation! Thank you.
Posted by Tarren | April 9, 2009, 3:36 AM