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?
I choose to solve this problem in a rather functional way so all you will need to do is get a list of all of the primes below 1 million and a function that simply tells if a prime is a circular prime or not. The method that I used to get the primes is the Sieve of Eratosthenes. This is just about the best way to generate primes for almost any project euler problem as it is very fast for generating the primes up to about 10 million, after that there are faster methods which you can employ if you ever need to. The code for just generating the primes is as follows:
def generate_primes(end):
primes = range(end)
for i in range(2,len(primes)):
if primes[i]: #This if statement never fires if we have already 'crossed' the prime out
for j in range(2*i,end,i):
primes[j] = None #crosses the prime out
if i**2 > end:
return filter(None,primes[2:]) #This simply filters out all of the Nones in the list
Next we need the function which tells if a prime is circular. I am going to make the assumption here that the list of primes that I have are all represented as strings, trust me it will be very simple if we make this assumption:
def is_circular(prime):
for i in range(len(prime)):
if prime[i:] + prime[:i] not in primes:
return 0
return 1
A refresher on how python handles string splicing: string[2:] will copy starting at the third letter and going to the end of the string while string[:2] will start at the first letter of the string and go to the third letter.
So the first time through the for loops prime[i:] will be prime[0:] which copies the entire string while prime[:0] copies nothing. In this way each letter of the string is rotated to the front and the entire string is matched against our current list of primes. If it ever is not found then false is returned. If the for loop runs all the way through true is returned.
So putting it all together we get:
def generate_primes(end):
primes = range(end)
for i ∈ range(2,len(primes)):
if primes[i]:
for j ∈ range(2*i,end,i):
primes[j] = None
if i**2 > end:
return filter(None,primes[2:])
def euler35():
def is_circular(prime):
for i ∈ range(len(prime)):
if prime[i:] + prime[:i] ¬∈ primes:
return 0
return 1
primes = map(str,generate_primes(10**6))
circulars = filter(is_circular,primes)
return len(circulars)
print euler35()
Which works at a horribly inefficient time of 5 minutes...
Fortunatly there is a solution. Past the primes 2 and 5 every prime ends in 1, 3, 7 or 9 and because each digit in a circular prime is rotated to the last digit at least once we can throw out every prime that contains a 2, 4, 5, 6, 8 or 0. This turns out to be a substantial number, and not only do we never have to check if these are circular, but when checking to see if a number exists in the list of primes having a smaller list greatly reduces the computational cost. So here is my final solution, which runs in only 2 seconds.
def generate_primes(end):
primes = range(end)
for i ∈ range(2,len(primes)):
if primes[i]:
for j ∈ range(2*i,end,i):
primes[j] = None
if i**2 > end:
return filter(None,primes[2:])
def euler35():
def is_circular(prime):
for i ∈ range(len(prime)):
if prime[i:] + prime[:i] ¬∈ primes:
return 0
return 1
primes = filter(lambda x: x.count('1') + x.count('3') + x.count('7') + x.count('9') == len(x),map(str,generate_primes(10**6)))
#idea to filter that junk out attributed to njlytoh in project euler fourms
circulars = filter(is_circular,primes)
circulars += ['2','5'] #these are added because they were originally thrown out
return len(circulars)
print euler35()
Hope you enjoyed it!
