Project Euler | Problem 3 | Largest prime factor



Problem Description :


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

Project Euler Problem 3 Solution in Java.
Project Euler Problem 3

Concept :


A number that is divisible by itself and 1 is called prime number. 

For example -

  1.   Prime factors of 12 are 2,2,3  and largest factor is 3.
  2.   Prime factor of  315 are 3,3,5,7 and largest factor is 7.

So here we have to find the largest prime factor of 600851475143 and we are using below algorithm.


Algorithm :


(source : GeeksforGeeks)


1)  While limit is divisible by 2.
  •  Add 2 into TreeSet.
  •  Divide limit by 2.

2) At this point limit should be odd. Write for loop that starts from i=3 and run until square root of limit.


 While limit is divisble by i.
  • Add i into TreeSet.
  • Divide limit by i.
increment i by 2 and continues.

3) If limit is prime number and greater than 2, then it won't become 1 by above two steps. So add limit to TreeSet if it is greater than 2.

4) TreeSet sort the elements in ascending order. So we will convert TreeSet to ArrayList and print last element of List because last element is largest prime factor.


Java Program :



Output :


Output of Project Euler Problem 3 - Largest Prime Factor in Java
Output - Project Euler Problem 3

References :


Thank you friends, I hope you have clearly understood the solution of this problem. If you have any doubt, suggestion or query please feel free to comment below. You can also discuss this solution in our forum.

Tags : Project Euler Problem 3 Solution, Mathematics problems, Largest prime factor, ArrayList, List, TreeSet, while loop, for loop, if statement.

About Author:

I am simple guy with lot of ambitions. My main motive is to share whatever knowledge I have related to programming. With me you can easily learn how to solve any programming problem in Java.You can connect with me on social networking sites also.


Let's Get Connected: Linkedin | Facebook |

Project Euler | Problem 3 | Largest prime factor Project Euler | Problem 3 | Largest prime factor Reviewed by Unknown on 11/09/2016 Rating: 5

No comments:

Please provide your valuable comments. If you have any suggestion please share with me I will work on it and if you have any question or doubt please ask, don't hesitate. I am your friend, i will clarify all your doubts.

Powered by Blogger.