素数的问题
程序如下:#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和它本身整除的数,但那里又是什么意思呢? 这是一个数学原理,基本上只要知道是这么做就OK,这里是为了避免输入数据过大,在递减数据求可除数时溢出,而使用的一种方法.......以下省略N千字的介绍 就是说等于一个数学公式这样吗? 差不多吧,好像与算法的时间度也有点关系.... 这句是精简算法的.
任何数的素数都不可能大于(他本身+1)的平方根.
开始用这句可以减少许多的遍历判断. 其他的优化算法还有,所有能被2整除的偶数也一定不是素数.所有位相加能被3整除的数也一定不是素数. 晕,这么多性质
页:
[1]