How to calculate the largest prime factor of a long number efficiently?

Question

I tried to create a Java program to calculate the largest prime factor of any long number (in this case 600851475143). When I try to run it, the program compiles indefinitely, without producing warnings or a result. I understand there might be easier/more straightforward ways to solve this problem, but I'm curious on the reason why this one doesn't seem to work. I don't think the logic itself is wrong, a possible error might be my use of long variables (I have not used them often before).

I have declared some variables as long to allow them the space to be increased to a 'long' size

    public class LargestPrimeFactor {
    public static void main(String []args){

        long num = 600851475143L;
        long largestPrimeFactor = 0L;
        boolean flag = false;

        //Find all factors of num
        for (long i = 2L; i <= num/2; i++){

            //If a number i is a factor of num
            if((num % i) == 0){

                //Find if the factor i is a prime number (only divisible by 1 and by itself)
                //by checking whether dividing it by any number results in an integer
                for (long j = 2L; j <= i/2; j++){

                    if (i/j == 0){

                        flag = true;
                    }
                    if (!flag){

                        if (i > largestPrimeFactor){

                            largestPrimeFactor = i;
                        }
                    }
                }
            }
        }
        System.out.print(largestPrimeFactor);
    }
}

Answer 1

Definitely, your code won't run infinitely. It's just that your code is not efficient and therefore it's taking too long to print the result. If you test with a smaller number or use an efficient code, you will get the result.

Given below is an efficient way of doing it:

public class Main {
    public static void main(String[] args) {
        long num = 600851475143L;
        long divisor = 2, largestPrimeFactor;
        while (num != 0) {
            if (num % divisor != 0) {
                divisor++;
            } else {
                largestPrimeFactor = num;
                num /= divisor;
                if (num == 1) {
                    System.out.println("The largest prime factor: " + largestPrimeFactor);
                    break;
                }
            }
        }
    }
}

Output:

The largest prime factor: 6857

Your code also has the following logical problems:

1. The variable, flag has been declared outside the outer loop which means that it will never be reset to false once it will become true.
2. Instead of checking i / j == 0, you need to check i % j == 0.
3. You should break the inner loop as soon as i % j == 0.
4. Also, the check for largestPrimeFactor needs to be moved from the inner loop to the outer one.

By the way, your test for primality is also not efficient. Instead of checking up to the half of the number, checking up to the square root of the number is sufficient. Check https://en.wikipedia.org/wiki/Primality_test for more details. Given below is an efficient code for primality test:

static boolean isPrime(int number) {
    boolean prime = true;
    if (number == 0 || number == 1 || number == -1)
        return false;
    for (int i = 2; i <= Math.sqrt(number); i++) {
        if (number % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}