for循环查找质数

Question

我正在尝试运行这段代码来打印所有小于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;
}

Answer 1

在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然后退出。

它不仅给出不正确的结果，而且到达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：在新版本中发现了一些bug。下面是修正后的版本：

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;
}

Answer 2

你在isPrime()中有一个bug

测试应该是：

if(n%i == 0) { ...

而且您需要从2开始计数，而不是从1开始计数，因为每个数字除以1后的余数都是零！

而且，不需要经过Math.sqrt(n)。

您应该将其更改为：

private static boolean isPrime(long n) {
    long max = (long)Math.sqrt(n);
    for (long i = 2; i < max; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

仅供参考，有了这个改变，我在我的PC上测试了程序，它在1秒内完成，给出了143064094810的结果

Answer 3

一个朴素的isPrime函数必须在每次运行时计算到i (或至少到sqrt(i))的所有素数。确保您的isPrime函数缓存其结果！