程序需要永远运行

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

我敢肯定,上面的程序不是无限循环.我测试了limit = 13195;并获得了理想的结果29

我不明白为什么我的CPU会永远运行它.

EDIT: 它是我的ProjectEuler.net第3号问题的代码.

Answer 1

您的算法的时间复杂度为O(n ^ 2),因此对于较大的限制值,它不是非常有效.

所以它很慢,因为你使用的算法很差.

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 iterations.这里面你调用isPrime()功能它也有一个for循环中它 for (int i = 2; i < number; i++)再有n iterations.所以基本上你有两个for循环,一个在另一个里面,这使你的时间复杂度n*n = n ^ 2