...
by MuYC @ 2019-07-18 08:48:31
要预处理
by royzhu @ 2019-07-18 08:48:50
首先
这道题目我们乍一看,黄题，好像不简单， 其实是我太水了
但是，分析后，你就会发现这道题的简单了。
思路：
看数据范围：m<=1000000,这样的话，如果你暴力，绝对会超时，所以，我们有好办法：先求出m内的所有素数，然后，我们就只要判断prime[i]<=R&&prime>=L就行了，这样的话，时间复杂度就会大大降低，我的总用时为：2651ms，虽然不是很快，但是跑起来不超时也是绰绰有余的。
关于如何筛选素数：
这道题的m范围不大，我们采用线性筛素数法，什么？不知道什么是线性筛素数法？ 我来给你先科普下吧。
线性筛素数法：又叫埃拉托斯特尼筛法
先简单说一下原理：
基本思想：素数的倍数一定不是素数 实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
说明：整数1特殊处理即可。
举个例子，N=20时，演示如下图：
我们找到一个素数后，把它m范围内的倍数全部标记，便于查找（一个素数的倍数一定是合数，小学生都知道的道理）
OK，要讲的都讲完了，下面贴代码：
```cpp
#include <bits/stdc++.h>
int prime[1000005]={0},t=0,m;
bool book[1000005];
using namespace std;
int check(int x){//线性筛素数模板
for(int i = 2;i <=sqrt(x);i++)
if(x%i==0)return 0;
t++;
prime[t]=x;//x进入素数列
for(int i = x+x;i <= m;i += x)
book[i]=1;//标记x的倍数
}
int main(){
int i,j,k,n,L,R,total;
cin>>n>>m;
for(i = 2;i <= m;i++){
if(book[i]!=1)
check(i);//如果i没有被标记过，就判断i是否为素数
}
for(i = 1;i <= n;i++){
cin>>L>>R;//判断R、L是否满足条件
if(R>m||L<=0||R<L)printf("Crossing the line\n");
else {
total=0;
for(j=1;j<=t;j++){//判断prime[j]是否满足条件
if(prime[j]>=L&&prime[j]<=R)total++;
else if(prime[j]>R)break;//当prime[j]>R，再往后也没意义了，退出循环。
}
printf("%d\n",total);
}
}
return 0;
}
```
我没成功审核通过的题解+1
by MuYC @ 2019-07-18 08:50:01
O(N^2\*sqrt(N))的时间复杂度显然过不了某些点
试试欧拉筛（线性筛）吧
by theaceblock @ 2019-07-18 08:50:48
楼上就是埃筛
by MuYC @ 2019-07-18 08:51:29
欧拉函数更强Orz
by MuYC @ 2019-07-18 08:52:05
# 谢谢各位大佬，我AC了
by judgejudge @ 2019-07-18 08:54:07
时间复杂度低。。好低/
by MuYC @ 2019-07-18 08:56:15
@[Aloor°川北](/space/show?uid=67817) 线筛和埃筛不一样吧
by Celestial_Scarlet @ 2019-07-18 08:57:00
@[Aloor°川北](/space/show?uid=67817) 不打同步赛了吗？
by Vanity_ @ 2019-07-18 09:00:49