Faster way to determine largest prime factor 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&lt;max; i++){
            for (int j=2; j&lt;=i; j++){
                if ((i % j == 0) &amp;&amp; (j != i))
                    isPrime = false;
            }

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

            isPrime = true;     //reset 
        }

        System.out.println("\n" + "the largest prime factor of the number 600851475143 is " + lgstPrime);
    }
}
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 &lt; 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 &lt; max; i++) {
    if (i == Integer.MAX_VALUE)
        System.out.println("will overflow now");
}


Better:

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




For readability, stick to one coding style:

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


Better:

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