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

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 - Project Euler Problem 3

References :

https://projecteuler.net/problem=3

http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

https://docs.oracle.com/javase/7/docs/api/java/util/List.html

https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

https://docs.oracle.com/javase/7/docs/api/java/lang/Math.html

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 | Google Plus