查人人中国名人网高岗夫人李立群:问一个素数求解过程中的简单问题
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/28 18:16:58
题目：判断101-200之间有多少个素数，并输出所有素数。
1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，
则表明此数不是素数，反之是素数。
2.程序源代码：
#include "math.h"
main()
{
int m,i,k,h=0,leap=1;
printf("\n");
for(m=101;m<=200;m++)
{ k=sqrt(m+1);
/* 这里为什么是m+1,而不是m?换成m,程序结果是一样的,和解? */
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);
}
1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，
则表明此数不是素数，反之是素数。
2.程序源代码：
#include "math.h"
main()
{
int m,i,k,h=0,leap=1;
printf("\n");
for(m=101;m<=200;m++)
{ k=sqrt(m+1);
/* 这里为什么是m+1,而不是m?换成m,程序结果是一样的,和解? */
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);
}
判断N是否为素数就要判断N除开1和它自身是否能被整除，而我们知道sqrt(N)*sqrt(N)=N，那么当判断了2到sqr(N)后就没有新的而没有判断的数了，比如判断了100/2，就没必要判断100/50，依次类推。
所以实际上只需要判断到sqrt(N),当N为小数时也可以不计算那么就是int(sqrt(n)).
至于你的问题为什么要m+1,估计是程序设计者考虑到计算机计算sqrt函数是要出现计算误差,比如sqrt(144)如果计算得出为11.99999后，经过类型转换就变成了11，那么也就只判断到11，而12则没判断到出现错误。
补充一点要求一个范围的素数，可以使用筛选发求解，速度要快很多。