Problem 35 Project Euler Solution with python

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?

Actually when I started writing code for this problem, I just thought of using itertools.permutations to get all the permutations of the number and then find the answer. But as I noticed "circular prime", then I changed the code and completed writing the program. In the first attempt the program took 214 seconds for execution. But as I started optimizing the code the execution time drastically reduced.

I took a lot of time optimizing the code, even I have optimized our previous Sieve of Erotosthenes to make this program faster.

You can see the explanation for sieve of Erotosthenes program we have used from here: Problem 7 Project Euler Solution with python.

We know that even numbers except 2 are all composite numbers(not prime). So from our sieve I have eliminated consideration for even numbers while looping. At the end while we create a list for prime numbers, I just added 2 so that the only even prime is added. You can see the same in the code and this is what I have optimized in sieve of Erathosthenes.

Now from here there are two parts in the program. As we start looping through prime numbers, first we are checking if any of the digit in the given prime number has 2,4,6,8,5,0 in it. If it has any of the digit then the flag is raised to False meaning that at any one circular permutation the number will not be a prime number. One more point to note is, there is no need for us to check the last digit of the given prime number, because if it had any of the above stated numbers then it wouldn't have been a prime number. According to me there are two advantages checking from tens digit. Obviously first being that we will reduce extra loops and second, numbers 2,5 will be able to pass the test.

Now in the second part firstly we will check if flag is True or false, if True we take the number and we will first assume that all the circular permutations of the number are prime. Then we create circular permutations of the number and if any of the number is found to be prime, then we will subtract 1 from the counter. We have subtracted 1 because we have added 1 to the counter in the starting of the loop thinking that all the circular permutations are primes.

That's it. As simple as it looks.

Have a look at the program and I am sure you will understand it for sure easily.

Program

File: pep35.py ------------------------- #http://radiusofcircle.blogspot.com #time module for calculation of execution time import time #time at the start of program execution start = time.time() #Sieve of Erotosthenes #One of the best algorithm to generate prime numbers #https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve(n): is_prime = [True]*n is_prime[0] = False is_prime[1] = False is_prime[2] = True #even numbers except 2 have been eliminated for i in xrange(3,int(n**0.5+1),2): index = i*2 while index < n: is_prime[index] = False index = index+i prime = [2] for i in xrange(3,n,2): if is_prime[i]: prime.append(i) return prime #sieving prime numbers upto 1 million primes = sieve(1000000) #counter to count the instances counter = 0 #looping through prime numbers for i in primes: #assuming that there is no 2,4,6,8,5,0 in digits flag = True #start with tens digit number = i/10 #looping through digits while number: if (number%10) % 2 == 0 or (number%10)%5 == 0: flag = False break number //= 10 #check if flag is true or false if flag: length = len(str(i)) number = i #assume that the circular permutations are prime counter += 1 #loop to create circular permutations for j in xrange(length): number = (number%10)*10**(length-1)+number//10 #if any permutation is not prime if number not in primes: #subtract one from counter counter -= 1 break #print the number of instances print counter #time at the end of program execution end = time.time() #printing the total time for execution print end - start

I think you will have to take a few numbers say 29, 53, 3 and substitute them in the code from line35 and even though it is tedious try to write the values of each and every variable. You will for sure understand what is happening if you haven't already.

As always you can download the source code from Github Gist pep35.py

Output

Summary

The first time I wrote a solution for this problem, as I made a mistake considering permutations of all the numbers instead of only circular primes, it not only gave me wrong answer, but the program also took a lot of time for execution. But after i have carefully read the question, I rewrote the code and then this time I got correct answer, but as I mentioned earlier the time of execution was beyond the prescribed limit. So I started refactoring the code and finally I was able to optimize the code from 215 seconds to less than about a second on my pc. I am really satisfied with the program. But I do think that there is a lot of scope for improvement.

One aspect I thought of optimizing the code was using dynamic programing, i.e memorizing the values that have been checked in the previous code, but this was found to be useless in my case. I will tell you why.

Number of primes below 1 million are 78000 approximately, out of which number of numbers that qualify the first round i.e digits without 2,4,6,8,0,5 are just 1000 approximately. So now if I will memorize the checked numbers and then for each and every iteration in the start if I will check if the prime is not in the checked list then I will end up consuming more resources and wasting some time. So I ignored that thought.

As always, if you have any doubt or didn't understand anything then you can comment in the comment box below and I will be glad to help you.

Please do comment if you have found any typo or have a different/better program or if you have any suggestions. I will be glad to view each of them.

You can also contact me.

Thank you. Have a nice day.

RADIUS OF CIRCLE

Search This Blog