Project Euler #3 in Java

Question

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: 1154999669

Questions:

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

Answer 1

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 <= 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.

---

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 -> Integer
intSqrt = floor . sqrt . fromIntegral

maxPrimeFact :: Integer -> 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 (<= intSqrt d) wheel
        | otherwise = go n maxPrime ws
        where
            (d, m) = n `divMod` w

problem3 :: Integer -> Integer
problem3 = maxPrimeFact

main :: IO ()
main = do
    _ <- getLine
    contents <- 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.

Answer 2

I tweaked your program to make it both faster and more correct (for arbitrary large test cases). Some of the things I changed:

1. Your counter i should be of type long. If you changed the test case to 600851475149L (a prime number), you would see that i would wrap around to a negative number at some point.
2. You should start your main loop at 1 in case NUMBER is prime.
3. Your main loop only needs to go to Math.sqrt(NUMBER). This is the key to keeping the run time bounded. Otherwise you may end up looping to a very large number in certain test cases.
4. Part of point #3 is that once you find a divisor i, in addition to checking if NUMBER/i is prime (as you already do), you should also check if i is prime.
5. You can skip even numbers in your main loop if you make sure NUMBER is odd by dividing out all factors of 2 initially.
6. The isPrime() loop can start at 3 and skip by 2.

Here is the final modified code:

public class PrimeFactorFinder {
    private static long NUMBER = 600851475143L;

    public static void main(String[] args) {
        long time   = System.nanoTime();
        long result = 1;

        // If NUMBER is even, get rid of all factors of 2.
        while ((NUMBER & 1) == 0) {
            NUMBER /= 2;
            result = 2;
        }
        // We only need to iterate to sqrt of the number.
        long end = (long) Math.sqrt(NUMBER);
        for (long i = 1; i < end; i += 2) {
            if (NUMBER % i == 0) {
                if (isPrime(NUMBER / i)) {
                    // This must be the largest prime.
                    result = NUMBER / i;
                    break;
                } else if (isPrime(i)) {
                    // This is a prime factor, but possibly not the largest.
                    // Record it as the largest prime factor so far.
                    result = i;
                }
            }
        }
        System.out.println("Result: " + result +
                "\nTime required to calculate in nanoseconds: " +
                (System.nanoTime() - time));
    }

    private static boolean isPrime(long l) {
        long max = (long) Math.sqrt(l);
        for(long num = 3; num < max; num+=2) {
            if(l % num == 0) {
                return false;
            }
        }
        return true;
    }
}

Output:

Original:
Result: 6857
Time required to calculate in nanoseconds: 774264336

Modified:
Result: 6857
Time required to calculate in nanoseconds: 6942153

Answer 3

Will modify the previous code soon. For now optimising the primality check.

    private static boolean isPrime(long l) {
        // Each prime number can be expressed as 6x+1 or 6x-1 except 2 and 3. Eliminate them.
        if(l<4){
            return true;
        }
        if(l%2==0 || l%3==0){
            return false;
        }
        // Best way to shorten the search is to navigate upto the sqrt of the number.
        long sqrt = (long)Math.sqrt(l);
        // That's right. We are incrementing the loop by 6 with 2 and 3 eliminated.
        for(long num = 6 ; num<=sqrt; num+=6) {
            if(l % (num-1) == 0 || (l%(num+1)==0)) { //Possible primes: 6x+1 and 6x-1 
                return false;
            }
        }
        return true;
    }

Answer 4

Here's my effort, which solves in ~240µs on an i7 iMac:

private long highest;

// checks if `f` is a factor of `n`,
// returning divided `n` accordingly
private long factorize(long n, long f) {
    if (n < f) return n;
    while (n % f == 0) {
        n /= f;
        if (f > highest) {
            highest = f;
        }
    }
    return n;
}

public long find(long n) {
    highest = 1;

    // check the two simplest cases
    n = factorize(n, 2);
    n = factorize(n, 3);

    // and then all numbers in the form 6x - 1 and 6x + 1
    if (n >= 5) {
        for (long i = 5; i * i <= n; i += 6) {
            n = factorize(n, i);
            n = factorize(n, i + 2);
        }
    }
    return (n == 1) ? highest : n;
}

This is a corrected version of @thepace's algorithm with special case tests for 2, 3, and then 6n - 1 and 6n + 1

Answer 5

Ok, here's a quick shot. Consider starting from the number 3 and increment your loops by 2?

Example:

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