Skip to main content

Problem 3 Project Euler Solution with Python

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

  The first method I tried was as follows:
#List to store all the divisible numbers
divisible = []

#Iterator for while loop
i = 2

#While loop to check if a number can divide
while i < 13195:
 if 13195 % i == 0:
  divisible.append(i)
  print i
 i = i+1

#Function to check if the number is prime
def isPrime(n):
 for i in range(2,n):
  if n % i == 0:
   return False
 return True


#A for loop to check for prime numbers
# in divisible list
for i in divisible:
 print i, isPrime(i)
As you can see my idea was to first generate all the numbers which can divide 13195(or 600851475143) and store them in a list named divisible. Next check if each and every number in the list is prime or not. Finally the largest number which is prime will be the answer.

 Even though this program worked for the example given in the problem, when I tried to apply similar code to the question(600851475143), it took more than 1 minute to just get the numbers which can divide 600851475143, which should not be the case according to Project Euler.

 So I had to frame another program to get the solution. I first searched on google "How to Factor a number", where I found this one: Wikihow Factor a Number. 

 Please see method 2 on wikihow Factor a number to understand the concept behind the program.It is suggested to recap again even if you know how to factor a number.

Program

The only thing I would like to explain in this program is the while loop which might be confusing for some of you.

Before I will explain, first see the following image, which has the factorization of the number 13195.
Prime Factors of 13195
Prime Factors of 13195
Now to be simple this is what is happening in the while loop. Lets understand the while loop iteration by iteration.
The while loop starts with i1 = 2. We are not considering the value of 1 and the number itself as we are finding the factors.
As the loop progresses till 5, 5 will be able to divide 13195 and thus the value of the number1 is changed from 13195 to 2639. Also the value of i1 is changed from 5 to 1, at the end of for loop a 1 is added and it again has a value of 2 which we had at the start.
This loop will run until the value of i1 is 7, and again the value of the number1 is changed from 2639 to 377. Again the value of i1 is changed to 2 at the end of for loop.
Loop again starts and this time it will run till the value of i1 becomes 13 and the value of number1 is changed to 29. 
This time there is no i1 which is able to divide 29 and the loop finishes. 
As you can see the last value of the number1 variable is the answer we require.
I have printed the same, so that we can see the output.

You can see or download the program from Github Gist if you want.

Output


Summary

This problem was pretty easy to solve. I think this problem can be solved in some other way which will reduce the execution time. But for now this is what I have. If you have a better code then please share it with me so that I we can together help the community.

 Coming back to code, I think you could have got lost at the while loop. I think I have thoroughly explained this part of code so that it will be easy for each and every one to understand. All the other part of code is well commented so that you can understand it easily. But if you have any doubt or didn't understand anything, comment in the comment box below and I will be glad to help you. You can also contact me if you want to.

 Please don't hesitate to comment below, if you want me to add any extra thing. Also please do help me if I have made any typo or any mistake.

 If you want you can 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