0 
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 的代码。

4

6 回答 6

9

您的算法的时间复杂度为 O(n^2)，因此对于较大的限制值不是很有效。

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

于 2013-09-05T10:23:59.107 回答
5

您的代码的时间复杂度为 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

于 2013-09-05T10:29:10.117 回答
2

这就是原因。

long limit = 600851475143L;

和一个 O(n^2) 算法，n 是这个长数600851475143L

于 2013-09-05T10:24:39.170 回答
2

您将每个 no 传递给 isPrime(long number) 方法，并且您再次使用了 for 循环“for (int i = 2; i < number; i++) {”，它每次都在为另一个 (number-1) 运行。表示您正在运行此 600851475141*600851475141 次。

你可能知道需要多少时间............也许你需要一个超级补偿......

快乐编码

于 2013-09-05T10:34:28.757 回答
1

正如所有人所说，您的代码不是很省时，但查看代码我可以猜想您正在努力寻找最大的主要因素，您实际上可以尝试 使用 Eratosthenes 的筛子来生成所有素数，然后从后面找到这个因素。

import java.util.LinkedList;

 class Sieve{



       public static LinkedList<Long> sieve(long n){
               if(n < 2) return new LinkedList<Long>();
               LinkedList<Long> primes = new LinkedList<Long>();
               LinkedList<Long> nums = new LinkedList<Long>();

               for(long i = 2;i <= n;i++){ //unoptimized
                       nums.add(i);
               }

               while(nums.size() > 0){
                       long nextPrime = nums.remove();
                       for(long i = nextPrime * nextPrime;i <= n;i += nextPrime){
                               nums.removeFirstOccurrence(i);
                       }
                       primes.add(nextPrime);
               }
               return primes;
       }
}

上面的代码返回素数的链表，使用这个从最后开始并得到你的最大因子。

注意：在运行输入600851475143L之前增加jvm 的堆大小

于 2013-09-05T10:43:52.207 回答
1

由于循环的嵌套（一个循环在 main 中达到限制，另一个循环在该循环内调用，在 isPrime 内），算法的时间复杂度为 O(n^2)。

这是一种标准的方式来表达一个算法需要多长时间来解决不同大小的输入的不同问题。

在您的情况下，大小是限制（600851475143L），因此要解决此问题将需要“600851475143 ^ 2 的订单”，相比之下，如果您的限制为10（例如）

因此，如果限制为 10 的版本需要 100 毫秒（10 的平方），那么您的 600851475143 版本将需要 361022495181519000000000 毫秒（即 600851475143L 的平方，如果我在那里弄错了一些零，请道歉）

时间复杂度的其他示例是 O(1) 或常数时间，其中算法花费相同的时间而不管大小，或 O(n) 或线性时间，其中花费的时间与大小成正比

于 2013-09-05T10:45:20.210 回答