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.您将2从1除以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;
}