且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

for循环查找素数

更新时间: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;
}