xmu 1246.素数筛选

1246.素数筛选
Time Limit: 2000 MS Memory Limit: 65536 K
Total Submissions: 802 (129 users) Accepted: 108 (69 users)
[ My Solution ]

Description
请求出区间[A,B]之间的素数的个数。

Input
输入有多组数据。
第一行为正整数T(T<10),表示输入的数据组数。
第二行到第T+1行，每行2个数字A,B(0

Output
输出T行数字，每行只有一个数字，表示对应的素数的个数。

Sample Input
2
100 200
2 1000000

Sample Output
21
78498

Source
Doraemon@xmu
[cpp] #include
#include
using namespace std;
#define N 46341
#define M 1000010
long long p[N],q[M],n,m,a[N],b[M];
void init()
{
memset(a,0,sizeof(a));
int i,j,gab=4;
a[2]=a[3]=1;p[0]=2;p[1]=3;n=2;
for(i=5;i {
if(!a[i])
{
a[i]=1;p[n++]=i;//if(i>=46000)cout< for(j=i;j*i a[i*j]=-1;
}
}
}
void cnt(long long l,long long r)
{
long long i,j,k,size=r-l;
if(r {
m=0;
for(i=l;i<=r;i++)
if(a[i]==1)m++;
}else
{
memset(b,0,sizeof(b));
for(i=0;i {
j=l/p[i];while(j*p[i] if(j<=1)j++;
for(;j*p[i]<=r;j++)
b[j*p[i]-l]=1;
}
m=0;
for(i=0;i<=size;i++)
if(b[i]==0)m++;
}
}
int main()
{
init();
long long t,l,r;
//for(int i=0;i<100;i++)cout< scanf("%lld",&t);
while(t--)
{

scanf("%lld%lld",&l,&r);
if(l<2)l=2;
cnt(l,r);
printf("%lld\n",m);
}

return 0;
}

#include
#include
using namespace std;
#define N 46341
#define M 1000010
long long p[N],q[M],n,m,a[N],b[M];
void init()
{
memset(a,0,sizeof(a));
int i,j,gab=4;
a[2]=a[3]=1;p[0]=2;p[1]=3;n=2;
for(i=5;i {
if(!a[i])
{
a[i]=1;p[n++]=i;//if(i>=46000)cout< for(j=i;j*i a[i*j]=-1;
}
}
}
void cnt(long long l,long long r)
{
long long i,j,k,size=r-l;
if(r {
m=0;
for(i=l;i<=r;i++)
if(a[i]==1)m++;
}else
{
memset(b,0,sizeof(b));
for(i=0;i {
j=l/p[i];while(j*p[i] if(j<=1)j++;
for(;j*p[i]<=r;j++)
b[j*p[i]-l]=1;
}
m=0;
for(i=0;i<=size;i++)
if(b[i]==0)m++;
}
}
int main()
{
init();
long long t,l,r;
//for(int i=0;i<100;i++)cout< scanf("%lld",&t);
while(t--)
{

scanf("%lld%lld",&l,&r);
if(l<2)l=2;
cnt(l,r);
printf("%lld\n",m);
}

return 0;
}