silitex 发表于 2010-10-19 16:29:44

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

由C语言的判断是否为素数所想到的问题
C语言有一个快速判断是否素数的计算方法：BOOL IsPrime(DWORD dwData)
{
    DWORD dwMax;
    DWORD i;
    BOOL bPrime = FALSE;

    if (dwData < 2)
      goto Label_End;

    dwMax = sqrt(dwData);
    for (i = 2, bPrime = TRUE; i <= dwMax; i++) {
      if (dwData % i == 0) {
            bPrime = FALSE;
            break;
      }
    }

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

gxqcn 发表于 2010-10-19 16:35:27

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

silitex 发表于 2010-10-19 16:37:57

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

果然独到啊！

gxqcn 发表于 2010-10-19 16:46:44

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

silitex 发表于 2010-10-19 16:53:43

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

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

无心人 发表于 2010-10-25 08:56:30

用圆整，而不是取整才好
页: [1]
查看完整版本: 由C语言的判断是否为素数所想到的问题