Problem #35 is one of the many questions on Project Euler that involves manipulating digits in primes. Here is the question:
Project Euler Problem 35: Circular Primes
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?
If you’ve seen any of my solutions to other problems involving counting primes less than an upper bound, you can probably guess what my solution will be.
Solution #1: Sieve Approach
We simply use the Sieve of Eratosthenes to list all primes less than or equal to 1,000,000 and then check each one for the circular ability. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #35
'''
import time
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if possible:
for x in range(i*i, (n+1), i):
primePossible[x] = False
myPrimes.append(i)
return [primePossible,myPrimes]
def projectEulerProblemThirtyFive(n):
allPrimeInfo = sieveEratosthenes(n)
primePossible = allPrimeInfo[0]
myPrimes = allPrimeInfo[1]
total = 0
for myPrime in myPrimes:
theString = str(myPrime)
found = False
for x in range(len(theString)):
if(not primePossible[int(theString[x:]+theString[0:x])]):
found = True
break
if(not found):
total+=1
return total
start = time.time()
print projectEulerProblemThirtyFive(1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
55
--- 0.270114898682 seconds ---
for input of n = 1000000
'''
As shown above, the Sieve of Eratosthenes continues to be invaluable for complex problems involving counting primes.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 