java - 求 2000000 以下的素数之和

Question

public static void main(String[] args) {
    int sum = 2;
    int isPrime;
    for(int x = 3; x < 2000000; x+=2){
        isPrime = 0;
        int y = 3;
        while(isPrime == 0) {
            if(x % y==0){
                isPrime = 1;
            }
            if(y > Math.ceil(x/2)) {
                isPrime = 1;
                sum+=x;
            }
            y += 2;
        }
    }
    System.out.println(sum);
}

上面的代码适用于 x < 1000，但我在 x = 2000000 时得到了错误的答案，并且我无法理解原因。

Answer 1

这是因为一个叫做 integer overflow 的东西。简而言之，它指的是计算机中的整数具有最大位数(即二进制中的数字)的概念。 int 的最大长度为 32 位，这意味着在无符号系统中最大可能的数字为 2^32-1。如果你在这个数字上加 1，你会得到 0，因为没有更多的数字可以携带 1!

因此，对于您的代码，请使用 long (有 64 位限制):

long sum = 2;
for(int i = 3 ; i < 2000000 ; i+=2) if(/*i is Prime*/) sum += i;
System.out.println(sum);

这是一个YouTube video这解释了它是什么。