Find the largest prime factor of a composite number

Project Euler Problem 3:  The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
Solution: Here we show a brute force approach to solve the above problem.


Java implementation of above is as follows:


//Find the largest prime factor of a composite number.
import java.io.*;
class FindLargestPrimeFactor{
int i=1;
long num;
String largestFactor="Not found";
void getNum(){
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
System.out.println("Enter the input :");
try{
String str = br.readLine();
num = Long.parseLong(str);
System.out.
println("Finding largest prime for :"+ num);
}
catch(IOException ie){}
}
void nextPrime(){
boolean b=true;
if(num == 0) //for num equals 0
return;
if(num == 1){ //for num equals 1
findFactor();
return;
}
for(i=2;i<=num;i++){ //for num greater than 1
if(i>100&&(i%2==0|i%3==0|i%5==0|i%7==0|
i%11==0|i%13==0|i%17==0|i%19==0|i%23==0))
continue;
//check if i is a factor of num
if(num%i == 0){
//now check if the factor is a prime
b = checkPrime(i);
if(b==true){
//now set largest variable
findFactor();
}
}
}
}
boolean checkPrime(int i){
int j=0;
if(i==2) return true;
for(j=2;j){
if(i%j == 0) return false;
}
return true;
}
void findFactor(){
if(num%i==0){
largestFactor = Integer.toString(i);
System.out.
println("Current largest factor is :"+largestFactor);
}
}
void displayResult(){
System.out.
println("Largest factor: " + largestFactor);
}
}
class Test3{
public static void main(String [] args){
FindLargestPrimeFactor x = new FindLargestPrimeFactor();
x.getNum();
x.nextPrime();
x.displayResult();
}
}

Much efficient implementation exist for the above problem. Keep Coding !!!

Leave a Reply

Your email address will not be published. Required fields are marked *