Prob 3

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