Faster way to determine largest prime factor

Question

Project Euler problem 3 asks:

What is the largest prime factor of the number 600851475143?

The first step I took is to determine the highest value number I should be looking at as a possibility (600851475143 / 2). Next I wanted to check each prime number as I go to see if it is a factor of 600851475143. If so, I store it in a variable denoting the highest prime factor encountered so far.

On running the program, the prime factor '6857' is the last output I am seeing for several minutes in my output. I entered this as the answer and it was correct. My problem is finding a way to streamline the algorithm to greatly reduce the processing time.

public class Euler3 {

    public static void main(String[] args) {
        long max = 600851475143L / 2;
        long lgstPrime = 1;
        boolean isPrime = true;

        for (int i=2; i<max; i++){
            for (int j=2; j<=i; j++){
                if ((i % j == 0) && (j != i))
                    isPrime = false;
            }

            if ((isPrime) && (600851475143L % i == 0))
                lgstPrime = i;

            isPrime = true;     //reset 
        }

        System.out.println("\n" + "the largest prime factor of the number 600851475143 is " + lgstPrime);
    }
}

Answer 1

My problem is finding a way to streamline the algorithm to greatly reduce the processing time.

Well, if we take into account that we are on Code Review, than an answer to this could be a little bit off the scope, as @HosamAly has already written, too. I will investigate this a little bit further.

Problems related to prime numbers are studied very extensive. The conclusion of this is, whatever you do, you will most probably just reinvent the wheel.

So the question should not be "how to reduce the processing time", it should be "how to handle my problem" which leads to the question of the problem definition. If your problem definition is just as mentioned "What is the largest prime factor of the number 600851475143?", then take the number, put it into Wolfram Alpha, and be done in 5 seconds.

If your problem definition is more like "How can I calculate the largest prime factor of a given integer?" Then find any algorithm/library, check if it is suitable and be done.

If your problem definition is a real world requirement, then find out the time constraint. It is always about time constraints for real world problems like this. Without a time constraint, you could improve it literally forever.

If your problem definition is more like "I want to improve my knowledge about coding and optimization in Java and I will try the problem xyz" Then there is no real answer to this. You could ask probably for some solutions on stackoverflow (as far as I got it, they do not like questions for euler problems there, so hide it a little bit. I would post an answer there if you link it).

Some suggestions about your code were already done, but I do not see the point in giving advices in optimization here.

---

My suggestions about the code:

long lgstPrime = 1;

Please write the full name, so everyone can read and understand it. Is it longestPrime, largestPrime, logarithmstPrime? You do not save real time or space by saving some characters (assuming we are in Java and not something like fortran77).

---

long max = 600851475143L;
for (int i = 2; i < max; i++) {
    ...
}

I do not think that your code will work and output anything. This is an infinite loop. Why? Because i is an integer, it will overflow at Integer.MAX_VALUE (2^31 - 1 or 2147483647) starting at Integer.MIN_VALUE or -2147483648 again. This will never reach max which is greater than 2147483647. So the loop will run forever.

Example to test:

final long max = 600851475143L;
for (int i = 0; i < max; i++) {
    if (i == Integer.MAX_VALUE)
        System.out.println("will overflow now");
}

Better:

long max = 600851475143L;
for (long i = 2; i < max; i++) {
    ...
}

---

For readability, stick to one coding style:

for (int i=2; i<max; i++){
      for (int j=2; j<=i; j++){
          if ((i % j == 0) && (j != i))

Better:

for (int i = 2; i < max; i++) {
    for (int j = 2; j <= i; j++) {
        if ((i % j == 0) && (j != i))

Answer 2

A much faster way to improve this algorithm is to do a Miller Rabin test on the first 12 or so primes, making sure that your number isn't one of the pseudo-primes in this list.

Assuming the Miller Rabin test tells you that it's composite, then if you want the factor, only trial divide the first 100 or so prime numbers. Then use pollard-rho to get any possible larger factors.

Further than that, I would have to know more about why you are doing this.

1. If you are doing this to learn Java coding or for your own fun, or for a homework assignment, then implementing the above would be best left as an exercise for you to do on your own.

2. If you are trying to solve a real world problem, much of the java code for this has already been written. For example, Richard Mathar implements the Miller Rabin test mentioned above in his Prime class. You can download his code here.

When I compared his algorithm on the number 3825123056546412223 (which is prime) to a trial division test I wrote, I got:

---

Miller Rabin test took 0.009 seconds to run.

Naive trial division takes 9.495 seconds to run.

---

A few comments to improve trial division

1. As has already been pointed out, you only need to test the numbers up to and including the sqrt(n).

2. If you don't want to store all of the prime numbers between 2 and n, one option after testing 2, 3, 5, and 7 is to keep track of the current number you are testing mod 3. The reason for this, is for example (7 % 3) = 1 so adding 2 will give you a number that's obviously divisible by 3. So if you want to end up with a number that's not divisible by 3 and also not divisible by 2, add 4 to get 11. Then (11 % 3) = 2, so obviously adding 4 is going to again, give you another number that's divisible by 3. So add 2 to get 13. Then (13 % 3) = 1.

To make that more efficient, notice that the current number % 3 is going to switch back and forth between 1 and 2, and the number you want to add is going to switch back and forth between 2 and 4.

This algorithm is simple to implement and will skip testing divisibility by any number divisible by 2 or 3 (assuming you start with a value that is not divisible by 2 or 3). The relevant code I use for this is:

// Assume that currvar is some number not divisible by 2 or 3
int mod3int = (currvar % 3);
// Put the below code inside of your loop
if (mod3int == 1) {
    currvar += 4;
    mod3int = 2;
} else {
    currvar += 2;
    mod3int = 1;
}
// Now test to see if your number is divisible by currvar

I imagine there are ways to make trial division even faster, but probably not worth wasting your time on. The Miller Rabin test mentioned above is going to be faster than probably any optimization on trial division you can come up with.

Answer 3

Your approach is naturally very slow. Let's calculate it together:

• For each number i between 2 and max, check whether it is prime.
• If i is prime, check whether it is a factor of your large number.

For i=10, you're doing 10 checks in the first loop. For i=100, you're doing a 100 checks. For i=1000, you're doing a 1000 checks. How many are these? This is called an Arithmetic Progression. When you've reached i=1000, you've made 1000*1001/2 = 500500 checks. At i=6857, you've made 23 million checks, and so on. Clearly you're not being efficient.

For the purposes of code review, think about the following optimizations:

• Why do you need to check whether i is prime? Think about it. Wouldn't it be faster to check whether (600851475143L % i == 0) directly? How many checks would your code perform if you use this approach, compared to your previous approach?

• In your inner loop, why do you need the condition j != i? Could you remove that, and suffice with j < i in the loop condition?

• When checking that whether a number is prime, do you need to check all the smaller numbers, or could it suffice to check a subset of them? To check whether 1009 is prime, do you need to divide it by 1008 or even 1000? Do you need to divide it by 700? Is there a smaller value where you can stop, and say confidently that this number is prime, because you checked all possibilities smaller than value?

• In addition to the previous point, can you think of a way to eliminate exactly half of all the values of j that you check?

Answer 4

You can use other techniques to find primes sieve of Eratosthenes:
But since this is a code review I will review the code you have:

The easiest optimization is to record primes as you go.
A number is prime if it is not divisible by any of the primes you have already found. Thus you don't need to check a number against all smaller numbers just all smaller primes.

public class Euler3 {

public static void main(String[] args)
{
   long max = 600851475143L / 2;
   long lgstPrime = 1;
   boolean isPrime = true;


   // I use ArrayList solely because I am too lazy to think of a better
   // dynamically expanding array structure. You may find that other
   // structures are better this is solely to demonstrate the algorithmic
   // change that can be done in the code.
   ArrayList<long>  primes = new ArrayList<long>();;
   primes.add(2);
   primes.add(3);

    // start at 5 ( we have added 2/3 and know 4 is not prime).
    // You should make this the same type as your max
    // Just in case sombody changes the value of max to something much bigger
    // without looking at the code.

    // We know that all even number are not prime.
    // So we can increment this loop by 2 each time.

    // With quick maths you see that multiples of 3 will hit multiples of 2 on even
    // multiples but not on add. So if you do increments of 2 followed by 4
    // then you will skip all the multiples of 2 and 3 thus removing a lot of numbers

    long inc = 2;
    for (long i=5; i<max; i += inc, inc = 6 - inc)
    {

       // Move this to the top of the loop
        // This makes the code eaaser to write.
        // As you show we are assuming prime and then checking
        // for failure.
        isPrime = true;     //reset 


        // Inner loop just loop over the primes:
        for (long j=0;j < primes.size(); ++j)
        {
            if (i % primes.get(j) == 0)
            {
                isPrime = false;
                break;          // As soon as you find the number is not prime
            }                   // break out of the loop.
        }    

        if (isPrime)
        {
            primes.add(i);
            if (600851475143L % i == 0)
            {
                lgstPrime = i;
            }
        }
    }
}

}