```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
}
}
```
DOWNLOAD

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