6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ How has no one mentioned the upper bound of the search space is much lower: i<(int)Math.sqrt(n); \$\endgroup\$ Mar 14, 2014 at 11:35
  • \$\begingroup\$ Even though trial division can tackle this one in reasonable time with any non-braindead implementation, consider using a faster integer factorization algorithm. Pollard Rho is very accessible and is considerably faster than trial division (its running time is asymptotically O(sqrt p) where p is the smallest prime factor of the input). A favourite for finding prime factors up to 50-60 bits. \$\endgroup\$
    – Thomas
    Mar 14, 2014 at 11:42

6 Answers 6

5
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ The Sieve of Eratosthenes will find many prime numbers. But which of those is the largest prime factor of 600851475143? Trial division is the way to go for this problem. \$\endgroup\$ Mar 14, 2014 at 4:56
  • \$\begingroup\$ Sieve of Eratosthenes is good for finding all prime numbers in some range, let's say all prime number up to a million, or all prime numbers from 13.1 billion to 13.2 billion. It is useless for checking if a single number is a prime, and it is useless for finding the largest prime factor of a number. \$\endgroup\$
    – gnasher729
    Mar 14, 2014 at 11:38
  • \$\begingroup\$ @gnasher729 It's far from useless to find the largest prime factor of a number. The efficiency hit comes from finding all the primes, not dividing them into the constant. So you find all the primes up to the desired number, then perform the division (iterating in reverse, from highest to lowest) to find the greatest one. The division is trivial, computationally, compared to the finding of the primes. (I also think there's some math which says you only need to find primes up to sqrt(num) or num/2 or something, but I don't remember well enough.) \$\endgroup\$
    – asteri
    Mar 14, 2014 at 13:39
  • 2
    \$\begingroup\$ The time that is needed to create the sieve far surpasses that which is needed to just perform the trial division. Even with a fast sieve creation. See my answer. \$\endgroup\$
    – Emily L.
    Mar 14, 2014 at 15:07
8
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ will give this a go \$\endgroup\$ Mar 13, 2014 at 22:04
4
\$\begingroup\$

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?

\$\endgroup\$
5
  • \$\begingroup\$ Come to think of it, this will also find factors that are not prime, so you'll probably want to run a probabilistic test on candidate results. Still faster than printing in order. \$\endgroup\$
    – Jessica
    Mar 13, 2014 at 22:05
  • \$\begingroup\$ yes it will find numbers that are not prime, I was aiming more for speed on this particular example, rather than something generic \$\endgroup\$ Mar 13, 2014 at 22:06
  • \$\begingroup\$ n is huge! Your best best is to optimistically hope to eliminate a few small factors quickly. For example, if n were divisible by 3, you would immediately reduce your search space by 66%. As it turns out, the smallest factor of n is 71, but that's still quite good: after 35 trial divisions, you reduce your search space by 98%! And when you're done, you know that the result is prime, with no further checking. \$\endgroup\$ Mar 14, 2014 at 6:09
  • 1
    \$\begingroup\$ The maximum for any factor is not the square root of n. Take 38 = 2 x 19. The largest factor is 19, much bigger than the square root of 38. What you mean is: If you haven't find any factor up to the square root of n, then you know it is a prime number. \$\endgroup\$
    – gnasher729
    Mar 14, 2014 at 11:54
  • \$\begingroup\$ Thanks, it's been a long time since I did prime-number things and I misremembered. Shame on me! \$\endgroup\$
    – Jessica
    Mar 14, 2014 at 19:34
3
\$\begingroup\$

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.
\$\endgroup\$
7
  • \$\begingroup\$ How do you know sqrt(n) is expensive to calculate? \$\endgroup\$ Mar 14, 2014 at 2:43
  • \$\begingroup\$ @NowIGetToLearnWhatAHeadIs: experience. In general an iterative algorithm is used that converge against the sqrt. (sometimes additional to a look up table with some starting points). For big n it may be faster to calculate sqrt(n) than checking up to n/2 but you have to profile where the break even point is. \$\endgroup\$
    – MrSmith42
    Mar 14, 2014 at 5:23
  • \$\begingroup\$ Ok. I was just asking because when I did this problem on project euler, I thought the same thing you are saying, but then I tried it with doing square roots and it was way faster. My processor has an FSQRT instruction, and I think java takes advantage of it when it does the square root. So its actually not so slow. But I am not 100% sure that java is doing the square root in hardware, but it certainly could be. \$\endgroup\$ Mar 14, 2014 at 5:41
  • \$\begingroup\$ How do you know sqrt (n) is expensive to calculate? Did you measure it? I bet you didn't. You tell someone to profile to find out whether they should use sqrt, but you haven't done any profiling yourself to find whether you should avoid it. This being 2014, a single square root is more expensive than most operations, but it is one square root and nowhere near as expensive as half a billion iterations through a loop if you look for prime factors of a number > one billion. \$\endgroup\$
    – gnasher729
    Mar 14, 2014 at 11:43
  • \$\begingroup\$ @gnasher729: You lost the bed. I profiled it years ago, and the result was that it was the bottle neck in my case. In my case an alternative implementation without sqrt was much faster. Therfore I wrote that only profiling can show if the costs of sqrt is higher than the alternative implementation. \$\endgroup\$
    – MrSmith42
    Mar 14, 2014 at 12:13
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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