[JZOJ 5458] 【NOIP2017提高A组冲刺11.7】质数 {欧拉筛}
题目
解题思路
这道题可以用欧拉筛线性筛)筛一下素数(时间复杂度为,然后暴力枚举一下素数 (时间复杂度大概为:)。
代码
#include<cstdio>
#include<cmath>
#define rr register
using namespace std;
int cnt,q,l[100002],r[100002],maxn,f[10000007],h[6000080];
bool b[10000007];
inline int maxx(int x,int y){ return x>y?x:y;}
void write(int x){if (x/10) write(x/10); putchar(x%10+'0'); }
inline int read()
{
int p=0; char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') p=(p<<3)+(p<<1)+c-'0',c=getchar();
return p;
}
int main()
{
q=read();
for (rr int i=1;i<=q;i++)
l[i]=read(),r[i]=read(),maxn=maxx(r[i],maxn);
int sq=sqrt(maxn);
for (rr int i=2;i<=maxn;i++)
if (!b[i]) {
h[++cnt]=i;
rr int g=i<<1; while (g<=maxn) b[g]=true,g+=i;
}
for (rr int i=1;i<=cnt;i++)
if (h[i]<=sq)
{
for (rr int j=i;j<=cnt;j++)
if (h[i]*h[j]<=maxn) b[h[i]*h[j]]=false; else break;
} else break;
for (rr int i=2;i<=maxn;i++)
if (!b[i]) f[i]=f[i-1]+1; else f[i]=f[i-1];
for (rr int i=1;i<=q;i++)
write(f[r[i]]-f[l[i]-1]),putchar('\n');
}