Skip to main content

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

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.
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more