由C语言的判断是否为素数所想到的问题

silitex

由C语言的判断是否为素数所想到的问题 C语言有一个快速判断是否素数的计算方法：

1. BOOL IsPrime(DWORD dwData)
2. {
3. DWORD dwMax;
4. DWORD i;
5. BOOL bPrime = FALSE;
7. if (dwData < 2)
8. goto Label_End;
10. dwMax = sqrt(dwData);
11. for (i = 2, bPrime = TRUE; i <= dwMax; i++) {
12. if (dwData % i == 0) {
13. bPrime = FALSE;
14. break;
15. }
16. }
18. Label_End:
19. return bPrime;
20. }

复制代码

这里的问题就在于dwMax，因为浮点数存储DWORD转换过来的值的时候，可能被转换成一个最近的double类型的浮点数，然后求了平方根以后，又转换成整数。 这个过程就存在了失真，是否有存在这种情况: dwMax所求出来的值满足如下条件：(dwMax+1)*(dwMax+1) <= dwData的情况？如果存在这种情况，那么这个判断素数的算法就有问题了。 望大家的解答！

gxqcn

这段代码应该存在问题，当dwData恰好为完全平方数时，dwMax可能会比理论值小1， 对于浮点数转整数，通常要加0.5。

silitex

这段代码应该存在问题，当dwData恰好为完全平方数时，dwMax可能会比理论值小1， 对于浮点数转整数，通常要加0.5。 gxqcn 发表于 2010-10-19 16:35

果然独到啊！

gxqcn

我为了避免这类问题，HugeCalc 就没调用任何浮点算法库，这样心里踏实些，感觉也更快。

silitex

我为了避免这类问题，HugeCalc 就没调用任何浮点算法库，这样心里踏实些，感觉也更快。 gxqcn 发表于 2010-10-19 16:46

是的，似乎一般写程序人员都是做能够100%确定的事情！谢谢您的解答！对我收益很大！

无心人

用圆整，而不是取整才好