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 < NUMBER; i++) {            if(NUMBER % i == 0 && isPrime(NUMBER / i)) {                result = NUMBER / i;                break;            }        }        System.out.println(Result:  + result + \nTime required to calculate in nanoseconds:  + (System.nanoTime() - time));    }    private static boolean isPrime(long l) {        for(long num = 2, max = l / 2 ; num < max; num++) {            if(l % num == 0) {                return false;            }        }        return true;    }}Output: Result: 6857 Time required to calculate in nanoseconds: 1154999669Questions:I am especially annoyed with the isPrime() method. Is there a better way to do this? How?Any general comments?
Project Euler #3 in Java
java;programming challenge
AlgorithmYour 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 <= 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 <= sqrt(3))[4 -> 2 -> 1] (factors: 2)[200 -> 100 -> 50 -> 25] --> [5 -> 1] (factors: 2, 5)[7007 -> 1001 -> 143] --> [13] (factors: 7, 11. 13 > 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.BenchmarksIn these benchmarks, my algorithm refers to the optimized version of the algorithm, as mentioned in the previous paragraph.OP's algorithm:Result: 6857Time required to calculate in nanoseconds: 870707572h.j.k.'s algorithm:Result: 6857Time required to calculate in nanoseconds: 864074780Slight improvement there, but not much.JS1's algorithm:Result: 6857Time required to calculate in nanoseconds: 10038730A 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 algorithmAverage time per trial (ns): 15507Algorithm: Alnitak's algorithmAverage time per trial (ns): 10880Looks like Alnitak's algorithm is faster.1000000 random intsGenerating a million random ints and feeding them in:Algorithm: wei2912's algorithmAverage time per trial (ns): 12337Algorithm: Alnitak's algorithmAverage time per trial (ns): 7661Alnitak'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 whereintSqrt :: Integer -> IntegerintSqrt = floor . sqrt . fromIntegralmaxPrimeFact :: Integer -> IntegermaxPrimeFact 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 (<= intSqrt d) wheel        | otherwise = go n maxPrime ws        where            (d, m) = n `divMod` wproblem3 :: Integer -> Integerproblem3 = maxPrimeFactmain :: IO ()main = do    _ <- getLine    contents <- getContents    let cases = map read $ lines contents    let results = map problem3 cases    mapM_ print resultsCredit must go to Martin R for the original solution.