Problem 3

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<Long> primeFactors(Long n){
         ArrayList<Long> facs = new ArrayList<Long>();
         long prime = 2;
         while(((double)n/(double)prime) != 1.0){
            if(n % prime == 0){
               n = n / prime;
               facs.add(prime);
            }
            else prime = nextPrime(prime);
         }
         facs.add(prime);
         return facs;
      }
 
      private static long greatestFac(ArrayList<Long> 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