10
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ This is too short to be a full-fledged answer so here it goes: you do not need to loop to half of l inside isPrime(), just its square root will do. \$\endgroup\$ – h.j.k. Dec 23 '14 at 3:07
  • 1
    \$\begingroup\$ @h.j.k. That didn't really help. It actually increased the time to calculate by about 100,000,000 nanoseconds. \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 3:10
  • \$\begingroup\$ good point, penalties of calculating square root... \$\endgroup\$ – h.j.k. Dec 23 '14 at 3:22
  • 1
    \$\begingroup\$ @MannyMeng the square root is essential - the problem is in your algorithm. In particular it's not necessary to perform a primality test for each iteration. \$\endgroup\$ – Alnitak Dec 24 '14 at 14:27
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Manny Meng I see that you've accepted my answer, thanks! :) I updated the answer after you accepted it to include benchmarks of all other answers in this question, so you can take a look. \$\endgroup\$ – wei2912 Dec 23 '14 at 17:34
  • \$\begingroup\$ Thanks for the illustration :) Will atleast correct my answer. I may not match what you have done. \$\endgroup\$ – thepace Dec 23 '14 at 18:06
  • \$\begingroup\$ Switched my answer to community wiki. \$\endgroup\$ – wei2912 Dec 23 '14 at 18:06
  • \$\begingroup\$ @wei2912 would you care to compare my version of thepace's solution against your other benchmarks? It runs in 240000 ns on my i7 iMac - about 10x faster than the best time you've quoted here. \$\endgroup\$ – Alnitak Dec 24 '14 at 18:03
  • \$\begingroup\$ Oops - was misreading the benchmarks, but this one should still be pretty quick \$\endgroup\$ – Alnitak Dec 24 '14 at 18:11
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ this is still pretty inefficient - it fails to divide the number being factored by each factor found in turn, and nor does it find repeated factors (unless they're 2) \$\endgroup\$ – Alnitak Dec 28 '14 at 11:03
2
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ Your algorithm has some errors that don't apply to the case in Project Euler but may affect other cases. Take a look at my answer for more details; it's in the benchmarks section, where I compared both of our algorithms. \$\endgroup\$ – wei2912 Dec 23 '14 at 17:35
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Your algorithm is faster than thepace's, beats mine for product of 2 large primes, and loses to mine for product of many small primes. Refer to my answer for more details. \$\endgroup\$ – wei2912 Dec 24 '14 at 18:52
  • \$\begingroup\$ @wei2912 I've updated, eliminating the sqrt call. \$\endgroup\$ – Alnitak Dec 24 '14 at 19:22
  • \$\begingroup\$ Your code does not work for 614889782588491410 which should give 47. \$\endgroup\$ – wei2912 Dec 25 '14 at 13:00
  • 1
    \$\begingroup\$ @wei2912 it gives 47 for me, so long as I add the L suffix. I do see a possible error where it might abort early for 6n - 1, though \$\endgroup\$ – Alnitak Dec 27 '14 at 20:29
  • \$\begingroup\$ That might explain. I'll check this in my free time. \$\endgroup\$ – wei2912 Dec 28 '14 at 8:10
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Didn't help much, but good point. \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 3:28
  • \$\begingroup\$ I managed to half the time when I applied the same changes for the main loop, not sure if you tried that as well. Here's hoping the rest can have much better suggestions... perhaps something that can take advantage of mathematical properties which I do not know of. :) \$\endgroup\$ – h.j.k. Dec 23 '14 at 3:30
  • \$\begingroup\$ And I managed to do so as well. This shows that the time-consuming part is the main method, and not isPrime() (well maybe it is). Never mind the last comment. \$\endgroup\$ – TheCoffeeCup Dec 23 '14 at 3:33
  • \$\begingroup\$ You can do better by going until max = Math.floor(Math.sqrt(number)), which is far less than number / 2. \$\endgroup\$ – Ryan Dec 23 '14 at 4:09
  • 1
    \$\begingroup\$ A correct solution should repeatedly divide the original number by the newly found factor, and only then take the new square root. \$\endgroup\$ – Alnitak Dec 24 '14 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.