Largest Prime Factor using BigInteger Class

Question

package Exercises;
import java.math.BigInteger;
public class LargestPrimeFactor {

    public static void main(String[] args) {
        BigInteger x = new BigInteger ("600851475143");
        BigInteger prime = new BigInteger ("0");

        for (BigInteger i = new BigInteger("2"); i.compareTo(x.divide(new BigInteger("2"))) < 1; i = i.add(new BigInteger("1")))
        {
            if (x.mod(i) == new BigInteger ("0"))
                if (isPrime(i))
                    prime = i;
        }
        System.out.println(prime);
    }

    public static boolean isPrime (BigInteger number)
    {
        for (BigInteger i = new BigInteger("2"); i.compareTo(number.divide(new BigInteger("2"))) < 1; i = i.add(new BigInteger("1")))
        {
            if (number.mod(i) == new BigInteger("0"))
                return false;
        }
        return true;
    }
}

so I'm trying to find the largest prime factor for 600851475143 but when i run it it doesn't display anything and it keeps running how can i fix this ?

Well, for starters you could use a more efficient prime check. — azurefrog, Jul 29 '17 at 20:45
Do you need to find the largest prime factor of a specific number (`600851475143`) or your input is not constant? — DAle, Jul 29 '17 at 20:50
Have you tested it with some lower numbers (`< 100`) where you know the correct result and can thus *confirm* that your algorithm even works, in general? — Zabuzard, Jul 29 '17 at 21:23
This algorithm need to be optimized, it takes really a long time. You can refer to the answer in [this link](https://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number) — caisil, Jul 29 '17 at 21:34

caisil · Answer 1 · 2017-07-29T21:31:05.237

2

There is a bug here. if (x.mod(i) == new BigInteger ("0")) suppose x=2, i=2, then x%i=0, but here will return a false, due to == will compare the address of the variable not the value.equals is a preferred one.

As @Zabuza suggested, I found a resource about the difference between == and equals.

edited Jul 29 '17 at 21:31

answered Jul 29 '17 at 21:17

caisil

363
2
14

You could improve the answer by adding a ressource that explains the difference between `equals` and `==`, for example another SO question with good answers, if you like. – Zabuzard Jul 29 '17 at 21:25
Also, you can print a debug message in the first for loop `System.out.println("DEBUG " + i);` – caisil Jul 29 '17 at 21:25
@Zabuza What is SO short for? – caisil Jul 29 '17 at 21:26
**SO** stands for **StackOverflow**, so the site we are currently at :) – Zabuzard Jul 29 '17 at 21:28

Largest Prime Factor using BigInteger Class

1 Answers1