the code doesn’t stop running, in Java
我正在用 Java 解决项目 Euler 中的问题 10，即
“The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.”
我的代码是
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
package projecteuler_1;
import java.math.BigInteger; public class ProjectEuler_1 { public static void main(String[] args) { public static boolean isPrime(int n) { |
但是代码没有给我任何结果，它没有停止运行。为什么？
- 代码在 O(n^2) 中，可能需要很长时间。确定完成了吗？
- 它打印什么？或者你是说它根本不打印任何东西？首先尝试使用更小的数字 – 正如@Absurd-Mind 所说，这可能需要很长时间。
- 一定需要时间。
- 它没有给你任何结果的原因是它的优化非常糟糕。 Project Euler 旨在针对需要它的问题优化您的算法，因此您的代码是解决方案过于简单而无法提供解决方案的主要示例。您需要制定另一种方法，但将其作为答案会破坏挑战。
- 它会完成，但需要很长时间。您应该考虑一些加快代码速度的捷径。例如： isPrime() 是否必须检查 n 下的所有数字，还是一个子集就足够了？也许你可以早点离开这个功能？等等 …
- @Absurd-Mind 不，虽然代码是正确的，但它没有完成，你怎么知道它在 O(n^2) 中？ :)
- 您是否尝试调试它？我和@Absurd-Mind 在一起，我相信它正在运行，但速度很慢。 2,000,000^2 = 4,000,000,000,000，这是很多
- @user3605253 尝试一个较小的数字，看看它是否真的运行正确。
- @user3605253 通过查看它。两个 while/for 循环表明它将是 n^2。尝试较小的数字或在 if (isPrime(n)) { print… 内添加打印
- 你知道 BigInteger 有自己的检查素数的方法吗？查看 BigInteger::isProbablePrime。
- 感谢@WillNess ….！
- @?·?§ù??± 不需要，真的。但不客气。 — 为什么要删除你的答案？我希望您已经进行了最后一次更正，因此这里至少有一个正确的代码，我可以对其进行投票。如果你这样做，请联系我。
- 在此搜索之前，此搜索提供了 15 个关于 SO 上有关此问题的问题。
- 我试图在 Java 中找到低于 200 万的素数之和的可能重复项
- @user3605253 遇到明显的非终止问题时，应用增长分析的经验顺序。为一些较小的 n 运行您的程序，您将在 1..10..100 秒范围内获得运行时间，然后为您的 n 进行投影。 — 至于你的代码，将你的 sum 设为 long 变量，而不是 int，然后在 isPrime() 函数中将 for (i = 2; i <= n / 2; i++) { 更改为 for (i = 2; i <= n / i; i++) {，它会为你工作。
通过一个小小的改变，你可以极大地提高性能：
变化：
|
1
|
for (int i = 2; i < n; i++) {
|
收件人：
|
1
2 |
你只需要检查到数字的平方根，因为在上升的过程中已经发现了更大的因素。
进行此更改会将您的算法从 O(n2) 更改为 O(n log(n))(我认为)。您的代码没有输出任何内容，因为运行时间太长 – 更改应该有望在合理的时间内为您提供答案。
- 我很想问为什么 OP 要检查偶数。如果它不除以 2，为什么它会除以 4？解决方案中还有其他问题，但我想我会把它留给 OP 去发现。
- @eis 您还可以进行其他优化，但即使您建议的优化也不会改变大 O 数。
- 是的，它没有。但是我认为我们不应该为他解决问题，因为 Project Euler 是关于个人学习的，真的。我认为他的算法次优的暗示应该足够了。
- 它将是 O(nsqrt(n))，而不是 O(nlogn)。为了推理，我在这个线程中给出了详细的答案。
- 仅供参考，所述问题是它”不会停止运行”，而不是”给出错误的结果”。我相信我已经回答了上述问题并提供了解决方案。
- (这并不能修复产生不正确结果的 OP 代码……只是提到它，因为这是一个公认的答案)。
您的代码运行时间是 O(n^2)。对 isPrime() 的每次调用平均为 O(n)。
解释：
1/2 可以被 2 整除，1/3 可以被 3 整除，… 1/n 可以被 n 整除。该方法的预期运行次数将是 (1-1/2) + (1-1/3) +…+(1-1/n) = (1+1+..+1)-(1/2+1/3+..+1/n) = n – (1/2+1/3+…+1/n) 第二个和是谐波数，它的和在 O(logn) 中，所以这给了你 O(n-logn)=O(n) 运行时间。
由于这是针对每个数字完成的，因此总共会给出 O(n^2).
@Bohemian 更改为 int max = Math.sqrt(n); 的方法将产生 O(nsqrt(n)) 性能，如该线程中所述。
就时间复杂度而言，最好的方法是使用像 Sieve of Eratosthenes 之类的东西，它会产生 O(nlogn) 时间性能，这在渐近上优于您的算法和优化的算法，因此对于大型算法运行速度会明显更快数字。
来源：https://www.codenong.com/23732444/
