Prime Number Calculator Not Working With Large Numbers

Question

I am trying to print out all the prime factors of a number. My code is as follows:

public static boolean isPrime(long n){

    long i = n;

    while (i > 0){

        if (n % i == 0 && !(i == 1 || i == n)){

            return false;

        }
        i--;
    }

    return true;

}


public static void primeFactors(long n){

    long i = n;
    while (i > 0){

        if (isPrime(i)){
            System.out.println(i);
        }
        i--;
    }

}

This code works for small numbers: 5, 5000,e.g. When I input 600851475143 to the method, my program runs and nothing is output. Why is this happening?

Answer 1

Your primality test function is horrible.

1. Quick win: count forwards not backwards. Currently you'll count through at lease half your number until you find a factor! That probably accounts for the delay you are observing.

2. Bit better: count odd numbers up to the square root.

3. Perhaps better still: count prime numbers up to the square root. precompute those using a sieve depending on the requirements.

Answer 2

Although the number is not out of long primitive value range (9,223,372,036,854,775,807), you should use BigInteger since BigInteger has function for this purpose and I think it is more efficient then other implementations including yours.

new BigInteger(yourNumer).isProbablePrime(100) // returns true or false

Furthermore primality test is done by using many mathematical approaches and algorithms, there are some ways which runs faster for numbers < 64bit and there are some which are better to test much larger numbers. There some other ways here

Answer 3

Change your method to the following:

public static boolean isPrime(long num) {
    for (int i = 2; i < Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Should be efficient enough.

Answer 4

When given the input number 600851475143, your program is printing nothing because the way you check for prime numbers is slow. Given enough patience, your program will print something - but this could be hours, days, even years. You would need to come up with a better algorithm for this calculation.

Answer 5

Short answer: the program actually isn't terminating. The method that you are using is one of the most inefficient ways to check for primes. Check out the Sieve of Eratosthenes for an easy to understand, fairly efficient algorithm.

Answer 6

no need to check n numbers to check if n is prime or no, It's enough to start from 0 to n/2:

public static boolean isPrime(long n){

        long i = 2;

        while (i < n/2){

            if (n % i == 0 ){

                return false;

            }
            i++;
        }

        return true;

    }

This will double performance

Answer 7

The other answers have focused on your function isPrime, which is inefficient. I will instead focus on your function primeFactors which is incorrect. Indeed, you can see that it prints primes up to n in reverse order, rather than the prime factors of n. Instead, do

public static void primeFactors(long n) {
  // Handle factors of 2
  while (n%2==0) {
    System.out.println(2);
    n /= 2;
  }

  // Handle all odd prime factors except the largest
  for (long p = 3; p*p <= n; p += 2) {
    while (n%p == 0) {
      System.out.println(p);
      n /= p;
    }
  }

  // Handle the largest prime factor
  if (n > 1) {
    System.out.println(2);
  }
}

You might notice that isPrime is never used! In fact it is not needed: as long as they are removed as you find them, all of the numbers you print will be primes.

There are many possible improvements here, but this method is fast enough as-is. One simple way would be to compute an upper bound of Math.sqrt(n) and compare p to it rather than multiplying p by itself each time. You might also want to check for 0 and negative numbers, and possibly 1, depending on how you want to handle those numbers.