|
Friday, 14 October 2011 18:41 |
import java.math.*;
import java.util.*;
public class Prob3{
public static void main(String[] argsv){
System.out.println("The largest prime factor of the number 600851475143 is " + greatestFac(primeFactors(600851475143l)));
}
private static ArrayList primeFactors(Long n){
ArrayList facs = new ArrayList();
long prime = 2;
while(((double)n/(double)prime) != 1.0){
if(n % prime == 0){
n = n / prime;
facs.add(prime);
prime = 1;
}
prime = nextPrime(prime);
}
facs.add(prime);
return facs;
}
private static long greatestFac(ArrayList list){
long high = list.get(0);
for(int i = 1; i < list.size(); i++){
if(list.get(i) > high) high = list.get(i);
}
return high;
}
// Find the next prime number after n (n + 1)
private static long nextPrime(long n){
n++; // remove if implementation details change (pass n + 1)
while(!isPrime(n)){
n++;
}
return n;
}
private static boolean isPrime(long n){
long limit = (long) Math.sqrt(n);
for(long i = 2; i <= limit; i++){
if(n % i == 0){
return false;
}
}
return true;
}
} // end class Prob3
 Read more: |
