代码不会停止运行，在 Java 中
•浏览 1
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."
我的代码是
package projecteuler_1;
import java.math.BigInteger;
import java.util.Scanner;
public class ProjectEuler_1 {
public static void main(String[] args) {
int sum = 0, i = 2;
while (i <= 2000000) {
if (isPrime(i)) {
sum += i;
}
i++;
}
System.out.println(sum);
}
public static boolean isPrime(int n) {
int i, res;
boolean flag = true;
for (i = 2; i <= n / 2; i++) {
res = n % i;
if (res == 0) {
flag = false;
break;
}
}
return flag;
}
}
for (int i = 2; i < n; i++) {
int max = Math.sqrt(n);
for (int i = 2; i <= max; i++) {但是代码没有给我任何结果，它没有停止运行。为什么？
通过一个小小的改变，你可以极大地提高性能：
变化：
package projecteuler_1;
import java.math.BigInteger;
import java.util.Scanner;
public class ProjectEuler_1 {
public static void main(String[] args) {
int sum = 0, i = 2;
while (i <= 2000000) {
if (isPrime(i)) {
sum += i;
}
i++;
}
System.out.println(sum);
}
public static boolean isPrime(int n) {
int i, res;
boolean flag = true;
for (i = 2; i <= n / 2; i++) {
res = n % i;
if (res == 0) {
flag = false;
break;
}
}
return flag;
}
}
for (int i = 2; i < n; i++) {
int max = Math.sqrt(n);
for (int i = 2; i <= max; i++) {收件人：
package projecteuler_1;
import java.math.BigInteger;
import java.util.Scanner;
public class ProjectEuler_1 {
public static void main(String[] args) {
int sum = 0, i = 2;
while (i <= 2000000) {
if (isPrime(i)) {
sum += i;
}
i++;
}
System.out.println(sum);
}
public static boolean isPrime(int n) {
int i, res;
boolean flag = true;
for (i = 2; i <= n / 2; i++) {
res = n % i;
if (res == 0) {
flag = false;
break;
}
}
return flag;
}
}
for (int i = 2; i < n; i++) {
int max = Math.sqrt(n);
for (int i = 2; i <= max; i++) {你只需要检查到数字的平方根，因为在上升的过程中已经发现了更大的因素。
进行此更改会将您的算法从 O(n2) 更改为 O(n log(n))(我认为)。您的代码没有输出任何内容，因为运行时间太长 - 更改应该有望在合理的时间内为您提供答案。
您的代码运行时间是 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) 时间性能，这在渐近上优于您的算法和优化的算法，因此对于大型算法运行速度会明显更快数字。