Speeding up my implementation of Project Euler #3

Question

Project Euler problem 3 asks for the largest prime factor of 600851475143.

I have gone from 96 lines to 17 lines taking hits at this one. This is what I am left with after all of that effort:

public class IntegerFactoriseFive {

    public static void main(String[] args)
    {
        long n = 600851475143L;
        for (long i = 2; i <= n; i++)
        {
            if (n % i==0)
            {
                System.out.println(i);
                n = n / i;
                i = 2;
            }
        }
    }
}

Is there any way to make it faster?

I'm not suggesting that it isn't quick enough already, but for the sake of it and for improving the way I tackle problems in the future. My other solutions were taking forever. I was using recursion, and I even only iterated up to the square root of the numbers I was checking (from early school maths I know to only check up to the square root, it is a lot quicker), but it was still to slow. In the end, iterating by one and dividing this huge number was the wrong way to go about it, so instead, I figured that dividing the number as much as possible was the only way I could do it in any good time.

Please offer suggestions. As you can see by the class name, it is my fifth official solution for it that is the quickest of the ones I came up with.

Answer 1

The Sieve of Eratosthenes is one of the most efficient prime-finding algorithms out there. If you really want a program with good performance, make sure to Google the clever methods that have already been devised. "Don't reinvent the wheel" is a common programming mantra.

As far as your implementation, there are a couple of simple logical notes (which I believe are covered by the other answers): don't check even numbers at all (increment with i += 2 rather than i++), and don't print until/unless it's absolutely necessary.

To address issues in the comments below: Division into the constant value is computationally trivial compared to the process of actually finding the primes. It's the finding that we want to speed up. After all the primes have been found which are less than the desired number, we can iterate over them from highest to least and find the largest one. It's pretty straightforward.

Answer 2

By inspection, n has no even factors. You only need to try odd factors.

Whenever you find an i that is a divisor of n, you should factor out all powers of i. There is also no need for i to start from scratch — your hunt for divisors should proceed monotonically upward.

Your search can end when i reaches or surpasses the square root of n. At that point, n is the answer to the challenge.

(A reasonable algorithm should obtain the answer within milliseconds.)

Answer 3

You're looking for the largest prime factor, right? And you know that the maximum for any factor will be the square root of n?

Why not run the loop from sqrt(n) backwards and break on the first result?

Answer 4

Reduce the number of System.out.println calls may give a little speedup:

public class IntegerFactoriseFive {

    public static void main(String[] args)
    {
        StringBuilder sb= new StringBuilder();
        long n = 600851475143L;
        for (long i = 2; i <= n; i++)
        {
            if (n % i==0)
            {
                sb.append(i).append('\n');
                n /= i;
                i = 2;
            }
        }
        System.out.println(sb.toString);
    }

}

You can also modify your algorithm.

1. If a number can not be divided by 2 it can also not be divided by any even number. So you can check2 and than only the odd numbers.
2. you can make a list of all little prime numbers and check these and from the point where you have not the primes, try all odd numbers
3. you can stop checking at sqrt(n) but that is quite expensive to calculate. Not so good, but still halves the work, stop at n/2.

Answer 5

There are some things you can do without resorting to a sieve to find all primes.

1. No even number besides '2' can be a prime so skip all even numbers in your iteration after removing all factors of '2'.
2. Limit your search range to the largest possible factor of n, i.e. Math.sqrt(n)

Like this:

public class IntegerFactoriseFive {
    public static void main(String[] args) {
        { // Original trial division
            long startTime = System.nanoTime();
            {
                long n = 600851475143L;
                for (long i = 2; i <= n; i++) {
                    if (n % i == 0) {
                        System.out.println(i);
                        n = n / i;
                        i = 2;
                    }
                }
            }
            long stopTime = System.nanoTime();
            System.out.println("ns: " + (stopTime - startTime));
        }
        { // Optimised Trial division
            long startTime = System.nanoTime();
            long n = 600851475143L;
            while (n % 2 == 0) {
                n = n / 2;
            }
            long largest = 0;
            for (long i = 3; i <= Math.sqrt(n); i += 2) {
                if (n % i == 0) {
                    largest = i;
                    while (n % i == 0) {
                        n = n / i;
                    }
                }
            }
            System.out.println(Math.max(largest, n));

            long stopTime = System.nanoTime();
            System.out.println("ns: " + (stopTime - startTime));
        }
        { // Optimised sieve+test
            long startTime = System.nanoTime();
            long n = 600851475143L;
            final int maxFactor = (int) Math.sqrt(n);
            boolean[] primes = new boolean[maxFactor + 1];

            for (int i = 0; i <= maxFactor; i++) {
                primes[i] = true;
            }

            long largest = 0;
            for (int i = 2; i <= maxFactor; ++i) {
                if (!primes[i])
                    continue;
                for (long j = ((long) i) * i; j <= maxFactor; j += i) {
                    primes[(int) j] = false;
                }
                if (n % i == 0) {
                    largest = i;
                    while (n % i == 0) {
                        n = n / i;
                    }
                if(n==1)
                    break;
                }
            }

            System.out.println(Math.max(largest, n));
            long stopTime = System.nanoTime();
            System.out.println("ns: " + (stopTime - startTime));
        }
    }
}

Output:

71
839
1471
6857
ns: 530011 (0.5ms)
6857
ns: 71469 (0.07ms)
6857
ns: 15287751 (15ms)

Summary: With a sieve based method, you need to spend so much time at generating the primes that it actually is slower than the original. If you need to test many numbers, then the sieve is going to overtake trial division as you only pay the setup once.

The optimized trial division is the fastest of them all by almost a factor 10.

Answer 6

Since you're increasing i from below, each time you find a factor it's actually a prime factor so you don't need to reset i to 2 after each finding:

1. check for n % 2 == 0 first and set n /= 2 in this case and jump to 1
2. Initialize i with 3
3. Initialize n_sqrt with sqrt(n)
4. if i > n_sqrt you're done. n is your highest prime factor
5. If n % i == 0 you found a prime factor, set n /= i and jump to 3
6. Increment i by 2 and jump to 4