Java 程序永远需要大量运行

Question

我正在编写一个 Java 程序来计算一个大数的最大质因数。但我对程序的复杂性有疑问，我不知道是什么导致程序永远运行大量数据，但它在处理少量数据时运行良好。

我的操作如下:

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

        }
    }

在这里，数组列表将包含数字的所有因数。所以我只需要获取素数，为此，我使用了一种方法来检查数字是否为素数，如果它不是素数，我将使用以下方法将其从列表中删除:

 java.util.ArrayList.remove() 

所以接下来的部分代码如下:

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


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

最后一行打印了最大数量的factorArray，这就是我要找的。

    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;
    }   

}

上面的函数是我在将数字从列表中删除之前用来确定它是否为素数的函数。

这个程序非常适合小数，但它需要很长时间才能给出大数的输出，尽管最后一个函数非常快。起初，我曾经在第一个循环中检查一个数字是否为质数，但速度更慢。

Answer 1

您正在循环 600851475143 个数字。

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

即使我们假设每次迭代花费的时间非常非常短(小至 1 微秒)，它仍然需要数天才能完成循环。

为了让这个程序运行得更快，你需要优化你的素数发现逻辑。

将迭代次数减少到合理数量的一种方法是循环直到数字的平方根。

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

或

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