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!

@MarounMaroun *one* looooooooooop would *not* be a problem. [Core i7 reaches 100 gigaFLOPS](https://en.wikipedia.org/wiki/FLOPS) so would finish it up in **6 seconds**. It's the second, *nested*, loop that turns 6 seconds into **2-4 days** of projected run time. :) (funny, log(600851475143) ~= 27, vs. 30 days in a month, so without the early break in the nested loop it would run for **2 months**). — Will Ness, Dec 28 '13 at 16:16
you don't need it. Besides, to save one `x%i`, you do a lot of `l%i`s. — Will Ness, Dec 29 '13 at 20:06
sorry, but i don't get the idea... i understand that i use a lot of l%i, but i can`t figure how to do it without it-.. — tobgirado, Dec 30 '13 at 03:20

NPE · Answer 1 · 2013-12-28T09:02:20.717

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

In addition, once a factor is found that way it is clear that it is prime. There is no need to test for primality separately. — Henry, Dec 28 '13 at 08:47
[prime factorization example](http://stackoverflow.com/questions/4273368/prime-factorization-program-in-java) — drhunn, Dec 28 '13 at 09:05

score 0 · Answer 2 · answered Dec 28 '13 at 08:50

0

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

answered Dec 28 '13 at 08:50

theNinja

129
1
1
10

solving it with the sieve of Er. up to sqrt(600G) should take ~ 2 mln operations (Nlog log N for N=775000). [Solving it with iterated trial division takes 1437](http://stackoverflow.com/a/15292911/849891). – Will Ness Dec 28 '13 at 16:12
Oops I guess using iterated division makes much more sense. – theNinja Dec 28 '13 at 17:15

Largest prime factor java

2 Answers2