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

silitex

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

1. BOOL IsPrime(DWORD dwData)
   
2. {
   
3.     DWORD dwMax;
   
4.     DWORD i;
   
5.     BOOL bPrime = FALSE;
   
6. 
   
7.     if (dwData < 2)
   
8.         goto Label_End;
   
9. 
   
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.     }
    
17. 
    
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%确定的事情！谢谢您的解答！对我收益很大！

无心人

用圆整，而不是取整才好