How to quickly find the largest prime factor?

Question

I have this code to find the largest prime factor for the number 600851475143:

    BigInteger tal = new BigInteger("600851475143");
    BigInteger tempBiggest = new BigInteger("2");
    BigInteger temp = new BigInteger("2");
    boolean check = true;

    for (BigInteger I = new BigInteger("2"); I.compareTo(tal) < 0; I = I.add(BigInteger.ONE)) {
        if (tal.mod(I).equals(BigInteger.ZERO)) {
            temp = I;
            if (temp.mod(new BigInteger("2")).equals(BigInteger.ZERO)) {
                check = false;
            } else {
                for (BigInteger t = new BigInteger("2"); t.compareTo(temp) < 0; t = t.add(BigInteger.ONE)) {
                    if (temp.mod(t).equals(BigInteger.ZERO)) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    tempBiggest = I;
                }
                check = true;
            }
        }               
    }
    System.out.println(tempBiggest);
    System.exit(0);

The code works for smaller numbers, but not for this large one. Is there a way to simplify this or is my entire code wrongly built?

Doesn't this fit in a `long`? And why check every possible factor, including even numbers? And why not stop at the square root? Anyway, as you'd expect, integer factorisation is one of the most heavily researched areas of computing, [pick your favourite](https://en.wikipedia.org/wiki/Integer_factorization). — biziclop, Feb 24 '16 at 20:10
There's plenty of answers to this specific question already. See also https://stackoverflow.com/questions/5042543/java-cant-make-projecteuler-3-work-for-a-very-big-number-600851475143 — Tennyson H, Feb 24 '16 at 20:11
"Quickly" is a relative term. For "smaller" numbers, you can do it in exponential time and it will take only a few seconds. For larger numbers, you are screwed (ie. (2^74,207,281-1)*(2^57,885,161–1)). If you come up with a polynomial time algorithm to factor any integer, publish it and collect your millions. Otherwise, it will take a long time for large numbers. See [here](https://en.wikipedia.org/wiki/Integer_factorization). — callyalater, Feb 24 '16 at 20:14

Daniel · Accepted Answer · 2016-02-25T07:53:15.880

2

This took my average computer less than 700 millis:

public static void main(String[] args) {
    long tal = 600851475143L;
    int i;
    for (i = 2; i <= tal; i++) {
        if (tal % i == 0) {
            tal /= i; i--;
        }
    } 
    System.out.println("largest prime factor is " + i); // largest prime factor is 6857
}

edited Feb 25 '16 at 07:53

answered Feb 24 '16 at 20:12

Daniel

6,194
7
33
59

2

This is by far the best answer because it properly divides the target number by each discovered prime factor, thereby dramatically reducing the work required. – that other guy Feb 24 '16 at 20:17
You should definitely loop only until sqrt(number). It does not matter for this concrete number because You are lucky, but for number like 60085147514371 You can speed it up about 25000 times. And by skipping even numbers even 50000 times. – Antonín Lejsek Feb 25 '16 at 02:56
@AntonínLejsek i'm afraid looping until `sqrt(60085147514371)` would result in a wrong answer, as the largest prime factor is **882450139** which is bigger than sqrt(60085147514371) = **7751460** – Daniel Feb 25 '16 at 07:56
@Daniel The logic would have to be a bit adjusted a bit as the remainder in `tal` can be (and in most cases would be) the largest prime factor too. – Antonín Lejsek Feb 25 '16 at 12:27
What does `tal /= i; i--;`mean? Is it some kind of for-loop? Cannot find anything about it. Thanks – Feb 25 '16 at 21:38
3

It's an implementation of the [Trial division](https://en.wikipedia.org/wiki/Trial_division) method. we divide the number by `i` until it's divisible no more, only than we increment `i`, once `i == number` we know that we've reached the largest prime factor (we know that `i` is a prime because otherwise we could've divided `number` by it, and we know it's the largest because we start the division from the smallest prime = 2). – Daniel Feb 25 '16 at 22:10

score 0 · Answer 2 · answered Feb 24 '16 at 20:09

First, loop only till sqrt(number).

Second, you can skip even numbers, so just check for mod(2) and then mod(3), mod(5) etc.

Third, during the run you can construct the list of successfully tested primes and then check mod() only on the items from that list. This will saves lot of time and you may forget about the second point.

Last, but not least - check variable is very confusing, rather move it into inner block, initialize always to true and forget about the last update for the next cycle.

score 0 · Answer 3 · answered Feb 24 '16 at 20:14

The largest prime factor can be at the most sqrt(num). So it will be better to start from that and then go down instead of going up. That way, as soon as you have a factor, you are done.

BigInteger sqrt = getApproxSquareRoot(num);
for (BigInteger t = sqrt; t.compareTo(2) > 0; t = t.add(BigInteger.ONE)) {
   // if t divides num then you found it.
}

score 0 · Answer 4 · answered Feb 24 '16 at 20:16

Your code is right but there are something you can change to make it run fast. For instance in the first cycle it is useless to proceed only adding one to i because you are considering every two steps a multiple of 2. Moreover you can check i.compareTo(sqrt(tal)) < 0; instead to avoid other useless loops. Furthermore I would think about a way to don't use check.

How to quickly find the largest prime factor?

4 Answers4