Largest prime factor java

Question

I'm needing a little help with this:

public class BiggestPrimeFactor{
        public static void main(String[] args){
            long biggest=0L;
            for(long i=2L; i<=600851475143L; i++){
                if(600851475143L%i==0){
                    for(int l=1; l<=Math.sqrt(i); l++){
                        if (i%l==0){
                            break;
                        } else{
                            biggest=i;
                        }
                    }
                }
            }
            System.out.println(biggest);
        }
    }//end of BiggestPrimeFactor

I don't know if it is okay or wrong, but it is taking way too much (more than half an hour then I got tired and closed command-line)...

Can you help or at least tell me if it is fine?

thanks!

i could solve it!!

this is what it does look like

public class BiggestPrimeFactor{
public static void main(String[] args){
    long x=600851475143L;
    long biggest=0L;
    for(long i=2L; i<=x; i++){
        for(long l=1L; l<=Math.sqrt(i); l++){
            if(l%i==0){
                break;
            } else{
                while(x%i==0){
                    x=x/i;
                    biggest =i;
                }
            }
        }
    }
    System.out.println(biggest);
}

}//end of BiggestPrimeFactor

and it took really little time! =P thanks for your help!

Answer 1

It seems that you are looking for the largest prime factor of 600851475143.

Once you have found a prime factor, you should repeatedly divide the target number by it. Only when you've done this should you proceed to checking further candidate factors. This will greatly reduce the amount of work your code has to do.

For example, once you've established that 600851475143 is divisible by 71, replace 600851475143 with 600851475143 / 71 = 8462696833 and so on.

Additionally, once a factor is found in this manner, it will automatically be known to be prime. There will be no need for a separate primality test (HT @Henry for pointing this out).

Here is a pseudocode implementation of the algorithm in question:

n = 600851475143
k = 2
m = None
while n > 1:
  while n % k == 0:
    m = k
    n = n // k               # integer division
  k = k + 2 if k > 2 else 3  # 2, 3, 5, 7, 9, ...
print(m)

(This pseudocode happens to be valid Python and takes 35 milliseconds on my computer.)

Answer 2

If you are going to call this method several times, you could optimize your search by building a list of primes. See Sieve of Eratosthenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Then start with the smallest prime and work your way up and stop when you reach the square root of the number (if you haven't found a prime factor yet).