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<A<=B<2^31,且B-A<2^20)表示區間的范圍。
Output
輸出T行數字，每行只有一個數字，表示對應的素數的個數。
Sample Input
2
100 200
2 1000000
Sample Output
21
78498
Source
Doraemon@xmu
[cpp] #include<iostream>
#include<cmath>
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<N;i+=gab^=6)
{
if(!a[i])
{
a[i]=1;p[n++]=i;//if(i>=46000)cout<<i<<" ";
for(j=i;j*i<N;j++)
a[i*j]=-1;
}
}
}
void cnt(long long l,long long r)
{
long long i,j,k,size=r-l;
if(r<N)
{
m=0;
for(i=l;i<=r;i++)
if(a[i]==1)m++;
}else
{
memset(b,0,sizeof(b));
for(i=0;i<n&&p[i]*p[i]<=r;i++)
{
j=l/p[i];while(j*p[i]<l)j++;
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<<p[i]<<" ";
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<iostream>
#include<cmath>
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<N;i+=gab^=6)
{
if(!a[i])
{
a[i]=1;p[n++]=i;//if(i>=46000)cout<<i<<" ";
for(j=i;j*i<N;j++)
a[i*j]=-1;
}
}
}
void cnt(long long l,long long r)
{
long long i,j,k,size=r-l;
if(r<N)
{
m=0;
for(i=l;i<=r;i++)
if(a[i]==1)m++;
}else
{
memset(b,0,sizeof(b));
for(i=0;i<n&&p[i]*p[i]<=r;i++)
{
j=l/p[i];while(j*p[i]<l)j++;
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<<p[i]<<" ";
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&l,&r);
if(l<2)l=2;
cnt(l,r);
printf("%lld\n",m);
}
return 0;
}
