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++)