似是而非的k=sqrt(n)

//题目：输入一个大于3的整数n，判定它是否为素数(prime，又称质数)
#include <stdio.h>
#include <math.h>
int main()
{int n,i,k;
printf("please enter a integer number,n=?");
scanf("%d",&n);
k=sqrt(n);
for(i=2;i<=k;i++)
if(n%i==0)break;
if(i<=k)printf("%d is not a prime number.\n",n);
else printf("%d is a prime number.\n",n);
return 0;
}

　　————谭浩强.《C程序设计》(第四版).p137,清华大学出版社

　　这个程序的代码首先输入需要判断的整数并存放在变量n中（其实这个变量定义为unsigned类型更理想，因为题目中已经明确是大于3的整数）。紧接着通过：

k=sqrt(n);

　　试图求出n的平方根或其平方根的整数部分。然而这个写法是有问题的，能否正确地按照希望求得n的平方根或其整数部分是得不到保证的。

　　这是因为sqrt()函数的函数原型是：

double sqrt (double);

　　也就是说，sqrt()函数的参数和返回值都是double数据类型。double类型属于浮点数据类型的一种，浮点类型并非像整数类型那样可以精确地表示整数，正相反，浮点数据类型用于近似地表示实数，尽管在个别情况下可以精确地表示，但就一般意义上而言，浮点数据类型只是对一定范围内的实数的一种近似表示。

　　因此，在k=sqrt(n)这个表达式中，不可能指望这个n是准确的，因为按照sqrt()函数原型的要求，这个n实际上表示的是(double)n，即调用时会存在类型转换，转换后的值为double类型，它是否精确等于原来的int类型的n值，一般而言是不清楚的。

　　或许有些对IEEE754标准很熟悉的人对此不能赞同——他们非常清楚在这个标准下浮点数的表示方法和内部结构。好吧，“不争论”，继续看下一个不确定性。

　　由于sqrt()函数的返回值是double类型，这表明sqrt()函数只承诺为我们求得实参的平方根的近似值——而不是像数学那样一定可以得到一个精确值。换句话说，当调用sqrt(9.)的时候，函数未必会精确地得到3.0这个数学上的精确的平方根，sqrt(9.)的值无论为3.000000000000001还是2.999999999999999 都有可能。这虽然是出于理性的判断，但也并非绝无经验事实作为佐证。试看下面的代码：

#include <stdio.h>

#include <math.h>

int main( void )

{

  int p , n = 4 ;

  p = pow( 10 , n );

  printf("%d\n", p );

  return 0;

}

　　在某些编译器上的输出结果是：

9999

　　这清楚地表明pow()这样的返回值为double类型的数学函数只是一种近似计算的函数。sqrt()这个数学函数也是如此，sqrt(9.)的值无论为3.0、3.000000000000001还是2.999999999999999都有可能。一旦sqrt(9.)的值为2.999999999999999，那么

k=sqrt(n);

　　将使k被赋值为2而不是预期中的3。这样代码中的下一句：

for(i=2;i<=k;i++)

的循环次数就会产生错误。这种错误在何时出现很难预料，但k=sqrt(n)是一个似是而非的表达则是确切无疑的。

　　这种未必立刻发作的错误比那些立刻就产生症状的BUG更可怕，它就像一颗不定时炸弹一样说不定什么时候造成损失。古代有则守株待兔的寓言，说的是某一天出现了兔子，你不能指望天天出现兔子。但这里的情形恰恰相反，尽管很多天都没出现兔子，但你保不准哪天就会突然窜出一只兔子。而一旦出现兔子，其严重后果则是你假定不会出现兔子时所无法预料的。

　　那么此时应该如何求n的平方根或其整数部分呢？实际上可以利用下面的数学常识轻易求得：

1=1^2
1+3=2^2
1+3+5=3^2
…
1+3+5+…+(2k1)=k^2

后面正确的代码应用了这个原理。

　　样本代码中的另一个问题是根本没有考虑输入一旦不小于3时应该如何处理，这样的一个严重后果是一旦用户误输入数据，比如输入了负数，程序将会发生悲惨的崩溃。在一个真正的软件中，绝对不能假设用户一定会正确地输入，否则可能带来非常严重且无法弥补的损失。

　　此外，代码中的输出部分过于啰唆繁复，后面的代码对此也进行了修正。

#include <stdlib.h>

int main( void )

{

  int n ;

  printf("请输入n的值\n");

  scanf("%d",&n);

  if( n <= 3)

     printf("输入不正确，程序退出\n");

  else

  {

     int n_ = n  , odd = 1  , k = 0  , i ;

     while( n_ >= odd )

     {

         n_ -= odd ;

         odd += 2  ;

         k ++ ;

     }

    for(i=2;i<=k;i++)

      if(n%i==0)

         break;

    printf("%d%s是素数\n" , n , (i > k)?"":"不");

  }

  return 0;

}

　　其中：

     while( n_ >=  odd )

     {

         n_ -= odd  ;

         odd += 2   ;

         k ++ ;

     }

　　用于求出n的平方根的整数部分。由于只需进行√n次整数的加减法运算，其效率方面也必定高于浮点运算的k=sqrt(n)。

巴特西

似是而非的k=sqrt(n)

最新文章

热门文章