@[UzumakiBoruto](/user/1152121)
这样枚举区间 $[l,r]$ 的素数个数肯定会 T 呀。
最坏时间复杂度为：$O(r_1 - l_1 + r_2 - l_2 + … + r_n - l_n)$。
by 2021zjhs005 @ 2023-12-03 16:38:38
筛法错了 @[UzumakiBoruto](/user/1152121)
by zyh0516_lucky @ 2023-12-03 16:39:55
@[UzumakiBoruto](/user/1152121)
或许可以考虑优化。
用一个 $vis$ 数组存 $i$ 是不是素数，如果是($vis_i = 1$）就直接 $cnt++$，否则判断一下，如果是，$vis_i =1$,$cnt++$；否则标记 $-1$。
一开始全是零。
如果遇到是零的需要判断，否则不用判断。
by 2021zjhs005 @ 2023-12-03 16:40:46
@[UzumakiBoruto](/user/1152121) [学习](https://www.luogu.com.cn/problem/P3383)
by zyh0516_lucky @ 2023-12-03 16:40:57
@[UzumakiBoruto](/user/1152121)
也可以用线性筛或者前缀和（就是统计区间内有多少个素数，最后 $a_r - a_{l-1}$ 。
by 2021zjhs005 @ 2023-12-03 16:41:57
时间复杂度弄错了，应该是：
$$\sum_{i=l_1}^{r_1} \sqrt{x_1} + \sum_{i=l_2}^{r_2} \sqrt{x_2} + \ldots + \sum_{i=l_m}^{r_m} \sqrt{x_m}$$
$$(l_i\le x_i\le r_i)$$
by 2021zjhs005 @ 2023-12-03 16:48:12
@[UzumakiBoruto](/user/1152121)
by 2021zjhs005 @ 2023-12-03 16:48:26
@[2021zjhs005](/user/1121995) [评测记录](https://www.luogu.com.cn/record/138063321)
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int n,m;
short primes[1000001];
inline bool in_m(int num1,int num2){
return (num1>=1&&num1<=m)&&(num2>=1&&num2<=m);
}
bool prime(int x){
if (!x||x==1) return false;
for (int i=2; i<=sqrt(x); i++)
if (!(x%i)) return false;
return true;
}
int main()
{
cin>>n>>m;
for (int i=1; i<=n; i++){
int l,r,cnt=0;
cin>>l>>r;
if (in_m(l,r)){
for (int i=l; i<=r; i++){
if (primes[i]==0){
if (prime(i)) {primes[i]=1;cnt++;}
else primes[i]=-1;
}
else
if (primes[i]==1) cnt++;
}
cout<<cnt<<endl;
}
else
cout<<"Crossing the line"<<endl;
}
return 0;
}
```
谢谢大佬
by UzumakiBoruto @ 2023-12-03 16:54:20