（一道很水的题）
（反正我第一眼看的时候也是这么想的）
题目背景
题目名称是吸引你点进来的
实际上该题还是很水的
题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line
输入输出样例
说明
【数据范围和约定】
对于20%的数据 1<=n<=10 1<=m<=10
对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000
-----------------------------------------------------------------------------------------------------------------
第一眼一看的时候
特别开心
这不就是求素数嘛！
看了一眼数据范围
还可以
用线性的欧拉筛应该可以
于是上手就写
（我才不会说我写了两遍，第二边上的时候思路才定下来）
好不容易写完了
结果输入数不进去
a[++l]写成了a[l++]
于是进入了死循环
哎
好不容易过了样例
一提交t了5个点
啊哈？？
不是线性的吗？？（顿时懵逼）
于是看题解了（千万千万不要这样，动不动就看题解，真的是很不好的习惯）
题解居然是埃氏筛
啊哈？？
再一看代码果然
先放一个我错误的代码！！！！！
以此为耻
#include<cstdio>
using namespace std;
long long n,m,a[],b[],c[],ans,len; //a存每个区间的素数个数，b存素数
long long l,r; inline long long read()
{
long long ans = ;
int p = ;
char ch = getchar();
while(ch < '' || ch > '')
{
if(ch == '-')
p = -;
ch = getchar();
}
while(ch >= ''&&ch <='')
{
(ans *= )+= ch-'';
ch = getchar();
}
return ans * p;
} int main()
{
a[] = ;
a[] = ;
b[] = ;
c[] = ;//0为不是
c[] = ;// 1为是
len = ;
n = read();
m = read(); for(long long i=;i<=m;i++)//遍历每个数
for(long long j=;j<=len;j++)//看他能不能被素数整除
{
if(i % b[j]== ) //被素数整除
{
a[i]=a[i-];
break;
}
else
if(j == len)//全用素数除过了
{
c[i] = ;
a[i] = a[i - ] + ;
b[++len] = i;
break;
}
} for(long long i = ;i <= n;i++)
{
l = read();
r = read();
if(l>=&&r <= m)//在范围内
{
if(c[l] == )
{
printf("%lld\n",a[r] - a[l]+);
}
else
{
printf("%lld\n",a[r]-a[l]);
}
}
else
printf("Crossing the line\n");
}
return ;
}
哎确实是循环多了好多
还是放题解！！！！！！
#include<bits/stdc++.h>
using namespace std; int f[];
bool vis[]; void shai(int n)
{
f[]=;
vis[]=true;
for(int i=;i<=n;i++)
{
if(vis[i]==false) //在筛里进行前缀和
{
f[i]=f[i-]+;//前缀和计算 这处
for(int j=i+i;j<=n;j=j+i)
{
vis[j]=true;//标记操作
}
}
else f[i]=f[i-];//前缀和转移 和这处就很妙了
}
} int main()
{
int n,m;
scanf("%d%d",&m,&n);
shai(n);
for(int i=;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
if(l< || r>n) cout<<"Crossing the line"<<endl;//判断是否超出区间
else
{
int y=f[r]-f[l-];//此处已经修改
cout<<y<<endl;
}
}
return ;
}
换个角度从判断素数，变成判断合数；
埃氏筛
本质上就是从2开始把它除本身的倍数全部删去，以此类推
区间和可以用前缀和处理；