小于200万的所有质数之和

Question

我试图找出所有小于 2,000,000 的素数之和，但它给出了错误的答案。我如何改进我的代码？我得到 1179908154 作为答案，但原始答案是 142913828922。

public class main {
    static boolean isPrime(int n) {
        if (n%2==0) return false;

        for(int i=3;i*i<=n;i+=2) {
            if(n%i==0)
                return false;
        }
        return true;
    }

    public static void main( String[] args) {
        int sum=2;
        for (int j=3;j<2_000_000;j=j+2){
            if(isPrime(j))
                sum+=j;
        }
        System.out.println("SUM : "+sum);
    }
}

Answer 1

int 最多只能达到 2^32，所以你有溢出。你必须使用长到 2^64.

此外，仅在值高达 200 万的列表上使用筛子来查找所有素数（更高效的算法）会更简单。然后通过筛子，总结所有找到的素数。您可以牺牲内存来换取更快的速度和更简单的代码。

Answer 2

更好的解决方案是 Sieve，它在 O(n) 时间复杂度下工作，我们得到所有小于 n 的素数，然后我们可以将它们相加。

小于200万的所有质数之和

Sum of all primes less than 2 million

java

primes