O(nm)是1e9的，你这明显要用前缀和O(1）查询，这能过是数据水了。
而且不管埃式筛还是线性筛都是橙色的吧...
by OIERljb @ 2024-04-01 20:58:08
有可能是造数据的时候有太多 `l < 1 || r > m` 的数据，如果造一组 1~m 的数据可以卡掉吧……
by zhouzihang1 @ 2024-04-01 20:59:58
我用的，也只是根号筛啊，不是埃氏筛和欧氏筛啊
by asd890123 @ 2024-04-02 17:04:33
而且别忘了，不只O(nm)，前面用根号筛保存1到m的数据时，还有O(m^(2/3))，当然也有常数优化
by asd890123 @ 2024-04-02 17:10:42
```
#include <cstdio>
#include <cstring>
int main(){
bool a[1000005];
int n,m,l,r,s[1000005];
s[0] = 0;
scanf("%d%d",&n,&m);
memset(a,1,sizeof(bool) * (m + 1));
a[0] = a[1] = 0;
for (int i = 2;i * i <= m;i++)
if (a[i])
for (int j = i * 2;j <= m;j += i)
a[j] = 0;
for (int i = 1;i <= m;i++) s[i] = s[i - 1] + a[i];
while (n--){
scanf("%d%d",&l,&r);
if (l < 1 || r > m) puts("Crossing the line");
else printf("%d\n",s[r] - s[l - 1]);
}
return 0;
}
```
现在会正解了，用时总计70ms（所有测试点只和），原先最长273ms，共960ms，但还是建议加强数据
by asd890123 @ 2024-04-18 17:08:43