c - 质数校验码中的怪异情况

Question

我在为 Project Euler 解题时，它让我求和所有 200 万以下的素数。这是我的代码:

#include<stdio.h>
#include<math.h>
int isPrime(int);
int main() {
    long long int sum = 0;
    int i; // index
    for(i = 2 ; i < 2000000 ; i++) {
        if(isPrime(i)) {
            sum += i;
        }
    }
    printf("%lli\n", sum);
}

int isPrime(int num) {
    int i; // index
    int sq = sqrt(num);
    for(i = 2 ; i <= sq ; i++) {
        if(num % i == 0) {
            return 0;
        }
    }
    return 1;
}

此代码得出正确答案 142913828922。但是当我将 isPrime() 中的 for 循环更改为:

for(i = 2; i <= sq+1; i++)   // or even sq+2, sq+3, etc.

导致142913828920、142913828917等错误结果

为什么会出错？理论上，它不会改变 isPrime() 发送到 main() 的数字，是吗？

Answer 1

如果将循环更改为

for(i = 2 ; i <= sq+1 ; i++)

然后 2 不再被认为是质数，因为您测试是否 2 % 2 == 0。

与您添加的更大的数字类似，越来越多的素数将不会被检测到。