Your current method relies on iterating through all numbers and checking if they're 1) a factor 2) is prime.
There's no need to check for primality if you look for the smallest factor, divide the number by that factor till it is no longer divisible by that factor, then continue. Not only are we able to skip the expensive primality check, but we're also able to reduce our search space massively (the upper bound is the maximum prime factor, in fact).
public static long maxPrimeFactor(n) {
for (int i = 2; i < n; i++) {
while (n % i == 0) {
n /= i;
}
}
return n;
}
I'm unable to provide benchmarks as I currently do not have JDK installed on my computer, but I believe that this should work quite well. My solution in Haskell finished this in barely noticeable time:
[wei2912@localhost]~/Workspace/wei2912/misc/projecteuler% time ./test.sh
6857
./test.sh 0.00s user 0.00s system 56% cpu 0.004 total
Note that this is a very informal benchmark. You would be better off benchmarking this function on your own.