Java program taking forever to run with large numbers

Question

I am writing a Java program that calculates the largest prime factor of a large number. But I have an issue with the program's complexity, I don't know what has caused the program to run forever for large numbers, it works fine with small numbers.

I have proceeded as follow :

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Largest_prime_factor {

public static void main(String[] args) 
{
    //ArrayList primesArray = new ArrayList();
    ArrayList factorArray = new ArrayList();
    long largest = 1;
    long number = 600851475143L ;
    long i, j, k;

    //the array list factorArray will have all factors of number
    for (i = 2; i < number; i++)
    {
        if( number % i == 0)
        {
            factorArray.add(i);

        }
    }

Here, the Array List will have all the factors of the number. So I'll need to get only the prime ones, for that, I used a method that checks if a number is prime or not, if it's not a prime number, I remove it from the list using the following method :

 java.util.ArrayList.remove() 

So the next part of the code is as follow :

for (i = 2; i < number; i++)
        {
         if (!isPrime(i))
         {
             factorArray.remove(i);
             System.out.println(factorArray);
         }
        }


        System.out.println(Collections.max(factorArray));
    }

The last line prints the largest number of factorArray, which is what I am looking for.

    public static boolean isPrime(long n) 
    {
        if(n > 2 && (n & 1) == 0)
           return false;
        for(int i = 3; i * i <= n; i += 2)
            if (n % i == 0) 
                return false;
        return true;
    }   

}

The function above is what I used to determine if the number is a prime or not before removing it from the list.

This program works perfectly for small numbers, but it takes forever to give an output for large numbers, although the last function is pretty fast. At first, I used to check if a number is prime or not inside of the first loop, but it was even slower.

Answer 1

You are looping over 600851475143 numbers.

long number = 600851475143L ;
for (i = 2; i < number; i++)

Even if we assume that each iteration takes very very small time (as small as 1 microsecond), it'll still take days before the loop finishes.

You need to optimise your prime-finding logic in order for this program to run faster.

One way to reduce the iterations to reasonable number is to loop until square root of number.

for (i = 2; i < Math.sqrt(number); i++)

or

for (i = 2; i*i < number; i++)

Answer 2

The calculation of the prime factors of 600851475143L should take less than a milli-second (with a not totally inefficient algorithm). The main parts your code is currently missing:

The border should be sqrt(number) and not number.
The current value should be checked in a while-loop (to prevent that non-prime-factors are added to the list, reduces range to check).
The max. value should be decreased (as well as the border) to number/factor after finding a factor.

Further improvements are possible, e.g. to iterate only over non-even numbers (or only iterate over numbers that are neither a multiple of 2 and 3) etc.

An example implementation for the same question on codereview (link):

public static long largestPrimeFactor(
        final long input) {
    ////
    if (input < 2)
        throw new IllegalArgumentException();

    long n = input;
    long last = 0;
    for (; (n & 1) == 0; n >>= 1)
        last = 2;
    for (; n % 3 == 0; n /= 3)
        last = 3;
    for (long v = 5, add = 2, border = (long) Math.sqrt(n); v <= border; v += add, add ^= 6)
        while (n % v == 0)
            border = (long) Math.sqrt(n /= last = v);
    return n == 1 ? last : n;
}

Answer 3

 for (i = 2; i < number; i++)
    {
        if( number % i == 0)
        {
            factorArray.add(i);

        }
    }

For an large input size, you will be visiting up to the value of the number. Same for the loop of removing factors.

   long number = 600851475143L ;

this is a huge number, and you're looping through this twice. Try putting in a count for every 10,000 or 100,000 (if i%10000 print(i)) and you'll get an idea of how fast it's moving.

Answer 4

One of the possible solutions is to only test if the the prime numbers smaller than the large number divide it. So I checked

        for (i=2; i < number; i++)
        {
            if(isPrime(i))
            {
                 if( number % i == 0)
                 {
                     factorArray.add(i);                    
                 }
            }   
        }

So here I'll only be dividing by prime numbers instead of dividing by all numbers smaller than 600851475143. But this is still not fast, a complete modification of the algorithm is necessary to obtain an optimal one.

Answer 5

@Balkrishna Rawool suggestion is the right way to go. For that I would suggest to change the iteration like this: for (i = 3; i < Math.sqrt(number); i+=2) and handle the 2 manually. That will decrease your looping because none of the even numbers except 2 are prime.