for循环查找素数 [英] for loop finding the prime numbers

问题描述

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

I am trying to run this code to print the sum of all the prime numbers less than 2 million. This loop is never ending. Can anyone tell me what is wrong with the code? It seems to work with smaller numbers though.

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测试除法：

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

这篇关于for循环查找素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！