杭州交通信息网中国进入新的发展阶段:★初学C++★求教小问题一个★
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/29 01:22:04
用VC++
分别求出[1，100]、[101，200]……[901，1000]中素数的个数
需要有函数调用
请写出主要程序
分别求出[1，100]、[101，200]……[901，1000]中素数的个数
需要有函数调用
请写出主要程序
题目：判断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);
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);
}
知道每个数是不是素数就行了，然后不就简单了。二楼的时间复杂度高了
用数组p[1001]，p[i]=0表示是素数，反之不是。
下面的函数就可以求出p[i]的值。
void init()
{
int i=1;
p[i++]=1;//1不是素数
for( ; i<=1000 ; i++)
{
if(p[i] == 1)
continue;
for(j=2 ; j*i<=1000 ; j++)
p[i*j]=1;
}
}
用素数的定义，对其中每个数判断就行了。