Project Euler #3 in Java Project Euler #3:

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Here is my solution:
public class PrimeFactorFinder {
    
    private static final long NUMBER = 600851475143L;

    public static void main(String[] args) {
        long time = System.nanoTime();
        long result = 0;
        for(int i = 2; i &lt; NUMBER; i++) {
            if(NUMBER % i == 0 &amp;&amp; isPrime(NUMBER / i)) {
                result = NUMBER / i;
                break;
            }
        }
        System.out.println(&quot;Result: &quot; + result + &quot;\nTime required to calculate in nanoseconds: &quot; + (System.nanoTime() - time));
    }

    private static boolean isPrime(long l) {
        for(long num = 2, max = l / 2 ; num &lt; max; num++) {
            if(l % num == 0) {
                return false;
            }
        }
        return true;
    }
    
}

Output:

 Result: 6857
 Time required to calculate in nanoseconds: 1154999669

Questions:

I am especially annoyed with the isPrime() method. Is there a better way to do this? How?
Any general comments?
Algorithm

Your current method relies on iterating through all numbers and checking if they're 1) a factor 2) prime.

With the new algorithm, 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 square root of the number).

public static long maxPrimeFactor(long n) {
    long factor = -1;
    for (int i = 2; i * i &lt;= n; i++) {
        if (n == 1) { break; }
        if (n % i != 0) { continue; }
        factor = i;
        while (n % i == 0) {
            n /= i;
        }
    }
    return n == 1 ? factor : n;
}


This algorithm is a slightly optimized version of Martin R's answer.

We first "trim" down a number by repeatedly dividing it by factors of itself which are smaller or equal to its square root. Here're some examples

[3] (no factors &lt;= sqrt(3))
[4 -&gt; 2 -&gt; 1] (factors: 2)
[200 -&gt; 100 -&gt; 50 -&gt; 25] --&gt; [5 -&gt; 1] (factors: 2, 5)
[7007 -&gt; 1001 -&gt; 143] --&gt; [13] (factors: 7, 11. 13 &gt; sqrt(143), hence it stops)


The square brackets represent groups of "divisions" where a number is repeatedly divided by the factor.

Most composite numbers will be reduced down to 1. This is because all prime factors of a composite number will always be lower than or equal to its square root. However, note that as an optimization, we trim down the upper bound to the square root of the new number upon every iteration. This results in a few cases where we stop at a prime number. In that case, we return that number, which is the largest prime factor.

Note that we only need to iterate through primes. Since a prime sieve is too expensive, iterating through {2, 3, 5, 7, ..., sqrt(n)} works well enough for our scenario. For clarity, my code iterates through all integers from 2 to sqrt(n); I'll leave this to the OP as an exercise.



Benchmarks

In these benchmarks, my algorithm refers to the optimized version of the algorithm, as mentioned in the previous paragraph.

OP's algorithm:

Result: 6857
Time required to calculate in nanoseconds: 870707572


h.j.k.'s algorithm:

Result: 6857
Time required to calculate in nanoseconds: 864074780


Slight improvement there, but not much.

JS1's algorithm:

Result: 6857
Time required to calculate in nanoseconds: 10038730


A definitely massive improvement, but is still a bit slow since the primality tests are too slow.

thepace's algorithm is currently a WIP.

From thepace's algorithm onwards, the benchmarks run too fast to be effective. Using 1000 trials:

Algorithm: wei2912's algorithm
Average time per trial (ns): 15507
Algorithm: Alnitak's algorithm
Average time per trial (ns): 10880


Looks like Alnitak's algorithm is faster.



1000000 random ints

Generating a million random ints and feeding them in:

Algorithm: wei2912's algorithm
Average time per trial (ns): 12337
Algorithm: Alnitak's algorithm
Average time per trial (ns): 7661

Alnitak's algorithm appears to be nearly 2 times faster. Great job to Alnitak! :)

I'd be glad to accept any suggestions for benchmarks.



My original solution in Haskell is as follows:

module Main where

intSqrt :: Integer -&gt; Integer
intSqrt = floor . sqrt . fromIntegral

maxPrimeFact :: Integer -&gt; Integer
maxPrimeFact n = go n 1 (2 : [3, 5..intSqrt n])
  where
    go 1 maxPrime _ = maxPrime
    go n _ [] = n
    go n maxPrime wheel@(w:ws)
        | m == 0 = go d w $ takeWhile (&lt;= intSqrt d) wheel
        | otherwise = go n maxPrime ws
        where
            (d, m) = n `divMod` w

problem3 :: Integer -&gt; Integer
problem3 = maxPrimeFact

main :: IO ()
main = do
    _ &lt;- getLine
    contents &lt;- getContents
    let cases = map read $ lines contents
    let results = map problem3 cases
    mapM_ print results


Credit must go to Martin R for the original solution.