素数的问题

august

程序如下：
#include "math.h"
main()
{
　int m,i,k,h=0,leap=1;
　printf("\n");
　for(m=101;m<=200;m++)
　　{ k=sqrt(m+1);
　　　for(i=2;i<=k;i++)
　　　　　if(m%i==0)
　　　　　　{leap=0;break;}
　　　if(leap) {printf("%-4d",m);h++;
　　　　　　　　if(h%10==0)
　　　　　　　　printf("\n");
　　　　　　　 }
　　　leap=1;
　　}
　printf("\nThe total is %d",h);

用这个数m除二到这个数的 sqrt(m+1) 是什么意思呢？ 我知道素数是只能被1和它本身整除的数，但那里又是什么意思呢？ [s:6]  [s:6]

Zelsazgh

这是一个数学原理,基本上只要知道是这么做就OK,这里是为了避免输入数据过大,在递减数据求可除数时溢出,而使用的一种方法.......以下省略N千字的介绍

august

就是说等于一个数学公式这样吗？ [s:3]

Zelsazgh

差不多吧,好像与算法的时间度也有点关系....

duzhi5368

这句是精简算法的.
任何数的素数都不可能大于(他本身+1)的平方根.
开始用这句可以减少许多的遍历判断.

duzhi5368

其他的优化算法还有,所有能被2整除的偶数也一定不是素数.所有位相加能被3整除的数也一定不是素数.

august

晕，这么多性质 [s:8]  [s:8]  [s:8]