素数检查代码奇怪的情况

2016-01-24 43 views 8 likes

当我解决项目欧拉问题时，它要求我总结所有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()，是吗？

来源

2016-01-24 quartercat

也许你使用过大的数字 – STF

回答

考虑你改变总和从142913828922到142913828920，则差值是2，这意味着你解释2不素。将sq更改为sq+1应该实现该差异。将其更改为sq+2最终会使3不是主要的。

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

等等。

来源

2016-01-24 09:05:58

非常感谢您！逻辑陷阱现在看起来并不棘手。 – quartercat

如果你改变了环路

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

然后2不再被认为是首要的，因为你测试是否2 % 2 == 0。

与您添加的较大数字相似，将不会像这样检测到更多和更多的素数。

来源

2016-01-24 09:02:52 Henry

这是更好地利用相反的

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

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

，以避免与sqrt函数这个问题

来源

2016-01-24 09:21:37 valdem

素数检查代码奇怪的情况

回答

相关问题