质数校验码中的怪异情况

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.

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

Answer 2

考虑到您将总和从 142913828922 更改为 142913828920，那么差值是 2，这意味着您将 2 解释为非素数。将 sq 更改为 sq+1 应该可以实现这种差异。将其更改为 sq+2 最终会使 3 不是质数。

((int)sqrt(2))+1 == 2
((int)sqrt(3))+2 == 3

等等。

Answer 3

最好用

for(i = 2 ; i*i <= num ; i++) {
    if(num % i == 0) {
        return 0;
    }
}

而不是

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

用 sqrt 函数避免这个问题

质数校验码中的怪异情况

Weird situation in prime number checking code

c

algorithm

primes