public class GreatestPrimeFactor {
    
    /* returns true if parameter n is a prime number, false if composite or neither */
    public static boolean isPrime(long n) {
        if (n < 2) return false;
        else if (n == 2) return true;
        for (int i = 2; i < Math.pow(n, 0.5) + 1; i++)
            if (n % i == 0)
                return false;
        return true;
    }

    /* returns smallest factor of parameter n */
    public static long findSmallestFactor(long n, long i) {
        if (n % i == 0) { // found it
            return i;
        } else if (i > n) { // can't find it; something's wrong
            return -1;
        } else { // keep trying
            return findSmallestFactor(n, i + 1);
        }
    }

    public static long greatestPrimeFactor(long n) {

        // finding smallest factor increases performance IMMENSELY with numbers this large.
        // for smaller numbers, just use:
        // for (long i = n / 2; i > 1; i--)
        long smallestFactor = findSmallestFactor(n, 2);
        for (long i = n / smallestFactor; i > 1; i--) // start with the largest factor and go down to 2
            
            if (n % i == 0) // check if it's even a factor before checking if it's prime
                if (isPrime(i)) // THEN check if it's prime (better performance to do it now instead of before)
                    return i;
        return n; // if it didn't already return something, there's nothing left to look for, so the number itself is prime
    }

    /* This function skips a lot of numbers by dividing by potential factors into the original number;
       it starts at the smallest factor, and continues until the largest factor (number / smallest factor) */
    public static long greatestPrimeFactor2(long n) {
        
        long smallestFactor = findSmallestFactor(n, 2);

        // this loops through the small factors first, but tests the large factors by dividing the number by the factors, i
        for (long i = smallestFactor; i <= n / smallestFactor; i++) // for the smallest factor to the largest factor (inclusive for both)

            if ((double)(n)/i == (int)(n/i) && n % n/i == 0) // if it's an integer and the number is divisible by the corresponding factor
                if (isPrime(n/i)) // THEN check if it's prime (better performance to do it now instead of before)
                    return n/i;

        return n; // if it didn't already return something, there's nothing left to look for, so the number itself is prime
    }
    
    public static void main(String[] args) {
        // examples
        System.out.println(greatestPrimeFactor(60)); // 5
        System.out.println(greatestPrimeFactor2(13195)); // 29
    }
}

              Created: February 16, 2014
Completed in full by: Michael Yaworski