运行程序需要很长时间[已关闭]

Question

询问代码的问题必须证明对所解决问题的理解程度最低。包括尝试的解决方案、为什么不起作用以及预期的结果。另请参见：堆栈溢出问题检查表

public class Problem_3 {
    public static void main(String... args) {
        long limit = 600851475143L;
        long largestPrimeFactor = 0;

        for (long number = 2; number < limit; number++) {
            if (isPrime(number)) {
                if ((limit % number == 0)){
                    largestPrimeFactor = number; 
                }
            }
        }       
        System.out.println(largestPrimeFactor);
    }

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

我敢肯定，上面的程序不是无限循环的。我用limited=13195；进行了测试，得到了想要的结果29

我不明白为什么我的CPU要花很长时间来运行它。

编辑：ProjectEuler的我的代码。网络问题3。

Answer 1

这就是原因。

long limit = 600851475143L;

一个O（n^2）算法，n是这个长数字

Answer 2

代码的时间复杂度为O（N^2）。所以对于大数来说，这不是一个好的算法。一个可能的建议如下——

你对最大的素数感兴趣，那么为什么不从最大的值开始呢？

    for (long number = limit-1; number > 1; number--) {
        if (isPrime(number)) {
            if ((limit % number == 0)){
                largestPrimeFactor = number;
                 break; 
            }
        }
    }  

虽然时间复杂度保持不变，但这肯定会比当前的算法减少时间。

但是，什么是时间复杂度...？？你是如何计算的...？？什么是O（N^2）？？请解释

 for (long number = 2; number < limit; number++)

以上是您的第一个for循环，您将在其中进行n次迭代。在这个函数中，您调用了isPrime（）函数，该函数中又有一个for循环（int i=2；i

Answer 3

您的算法的时间复杂度为O（n^2），因此对于较大的极限值，它不是非常有效。

所以它很慢，因为你使用的算法很差。