Project Euler | Problem 3 | Largest prime factor
Problem Description :
![]() |
Project Euler Problem 3 |
Concept :
For example -
- Prime factors of 12 are 2,2,3 and largest factor is 3.
- 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 :
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.
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.
- Add i into TreeSet.
- Divide limit by i.
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 :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.javamultiplex.projecteuler; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.TreeSet; | |
/** | |
* | |
* @author Rohit Agarwal | |
* @category Project Euler Problem 3 | |
* @problem largest prime factor | |
*/ | |
public class Problem3 { | |
public static void main(String[] args) { | |
// We have to find largest prime factor of 600851475143. | |
long limit = 600851475143L; | |
/* | |
* 1. We are using Set for storing factors,as we know factors can be duplicate and we don't wan't duplicate. | |
* 2. TreeSet will sort the factors in ascending order, thats why we are using it. | |
*/ | |
TreeSet<Integer> factors = new TreeSet<Integer>(); | |
// Condition1:Reducing the limit,dividing it by 2 till limit%2==0. | |
while (limit % 2 == 0) { | |
factors.add(2); | |
limit = limit / 2; | |
} | |
/* | |
* Condition2:At this point we don't have multiple of 2, thats why we | |
* are skipping even numbers(i=i+2). | |
*/ | |
for (int i = 3; i <= Math.sqrt(limit); i = i + 2) { | |
// Same as Condition1. | |
while (limit % i == 0) { | |
factors.add(i); | |
limit = limit / i; | |
} | |
} | |
/* | |
* | |
* After Condition1 and Condition2 we will get limit that is prime | |
* number and greater than 2. | |
*/ | |
if (limit > 2) { | |
factors.add((int) limit); | |
} | |
/* | |
* Converting TreeSet to ArrayList, because we want largest factor. That | |
* is last element of the list. | |
*/ | |
List<Integer> list = new ArrayList<Integer>(factors); | |
int size = list.size(); | |
int lastElement = list.get(size - 1); | |
System.out.println("The largest prime factor of the number 600851475143 is: " + lastElement); | |
} | |
} |
Output :
![]() |
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.
Project Euler | Problem 3 | Largest prime factor
Reviewed by Rohit Agarwal
on
11/09/2016
Rating:

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.