题目:计算2个整数之间的素数。 给定2个整数A≤B <10 5,从A到B(含B)的素数是多少。
输入:多达1000行,每行包含2个由空格分隔的整数A和B。当A = B = -1时,输入终止(不处理此行)。
输出:对于输入中的每一行–除了最后一行(其中A = B = -1)-打印A和B之间(包括首尾在内)的质数数。
样本输入
0 9999
1 5
-1 -1
1 5
-1 -1
样本输出
1229
3
3
代码
#include<stdio.h>
#include<string.h>
int main()
{
int a,b,i,j,x,count;
int m[100002]= {0};
while(scanf("%d %d",&a,&b)&&a!=-1&&b!=-1)
{
memset(m, 0, sizeof m);
for(i=2; i<=100002; i++)
{
if(m[i]==0)
for(j=i*2; j<=100002; j+=i)
m[j]=1;
}count=0;
for(i=2; i<=100002; i++)
{
if(m[i]==0)
count++;
m[i]=count;
}
if(a>0)
x=m[b]-m[a-1];
else
x=m[b]-m[a];
printf("%d\n",x);
}
return 0;
}