gpt4 book ai didi

java - for 循环查找素数

转载 作者:行者123 更新时间:2023-12-03 21:03:04 25 4
gpt4 key购买 nike

我正在尝试运行此代码以打印所有小于 200 万的素数的总和。这个循环永无止境。谁能告诉我代码有什么问题?不过,它似乎适用于较小的数字。

public static void main(String[] args) {

long result = 1;

for(int i=0; i<2000000; i++) {
if(isPrime(i)) {
result+= i;
}
}
System.out.println(result);

}
private static boolean isPrime(long n) {
boolean result = false;

for(long i=2; i<(long)Math.sqrt(n); i++) {
if(n%i == 0) {
result = false;
break;
}
else result = true;
}
return result;
}

最佳答案

isPrime 中,您只测试除以 2:

private static boolean isPrime(long n) {
boolean result = false;

for(long i=1; i<n/2; i++) {
if(n%2 == 0) {
result = false;
break;
}
else result = true;
}
return result;

}

它应该除以每个 i 并从 2 开始:

for(long i=2; i<n/2; i++) {
if(n%i == 0) {
...

实际上在您当前的版本中,奇数 n 将一直除以 2 直到 n/2 而不是很快停止。考虑 n = 21。您正在从 1 到 10 除以 2,而不是在第 3 步除以 3 并退出。

它不仅给出了错误的结果,而且花费的时间也比到达 return 语句所需的时间长得多。

编辑:要获得更快的结果,请查看这个 Erathostenes 筛法:

public static long sumOfPrimes(int n) {

long sum = 0;

boolean[] sieve = new boolean[n];
for(int i = 2; i < Math.sqrt(n); i++) {
if(!sieve[i]) {
for(int j = i * i; j < n; j += i) {
sieve[j] = true;
}
}
}

for(int i = 2; i < n; i++) {
if(!sieve[i]) {
sum += i;
}
}

return sum;
}

编辑 #2:发现您的新版本存在一些错误。这是更正后的:

private static boolean isPrime(long n) {
boolean result = false;

if(n == 2 || n == 3) return true;

for (long i = 2; i <= (long) Math.sqrt(n); i++) {
if (n % i == 0) {
result = false;
break;
} else
result = true;
}

System.out.println(n + " " + result);
return result;
}

关于java - for 循环查找素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10880669/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com