更新时间:2023-02-26 17:52:36
在 isPrime
你只是按2测试除法:
In isPrime
you are only testing division by 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;
}
它应按每划分我
并从2开始:
for(long i=2; i<n/2; i++) {
if(n%i == 0) {
...
实际上,在您当前的版本中,奇数 n
将继续除以2到 n / 2
而不是很快停下来。考虑n = 21.你将2从1除以2,而不是在第3步除以3并退出。
Practically in your current version an odd number n
will keep dividing by 2 up to n/2
instead of stopping much sooner. Consider n = 21. You are dividing by 2 from 1 to 10, instead of dividing by 3 at the 3rd step and exiting.
它不仅给出了不正确的结果,而且也需要比达到返回
声明所需的时间更长的时间。
It not only gives incorrect results, but also takes much longer than needed to reach a return
statement.
编辑:对于更快的结果检查这个Erathostenes方法的筛子:
Edit: For faster results check out this sieve of Erathostenes method:
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 :发现一些错误新版本。以下是更正的:
Edit #2: Found some bugs with your new version. Here's the corrected one:
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;
}