前缀和优化一下
by wcyQwQ @ 2022-08-02 13:43:00
@[wuzijin](/user/724593)
1. 在函数内定义 `int l[n+5]={0}` 绝对是坏习惯。
2. $n\sqrt n$ 的复杂度严重不合法
by Etinorally @ 2022-08-02 13:43:55
@[wuzijin](/user/724593) 试除法本题可以过，但要预处理出1到m中所有的质数
by GalwayGirl @ 2022-08-02 14:10:24
```cpp
#include<bits/stdc++.h>
using namespace std;
int dp[1100000],n,m,l,r;
int main()
{
cin>>n>>m;
for(int i=2;i<=m;i++)
{
int flag=0;
for(int j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag==0)dp[i]=dp[i-1]+1;
else dp[i]=dp[i-1];
}
for(int i=1;i<=n;i++)
{
cin>>l>>r;
if(l<1||r>m)
{
cout<<"Crossing the line"<<endl;
continue;
}
cout<<dp[r]-dp[l-1]<<endl;
}
return 0;
}
```
by GalwayGirl @ 2022-08-02 14:10:54
试求质数筛法（埃式）
by Allen_yang @ 2022-09-03 18:40:32
欧式
by SaintRelief @ 2022-11-25 11:23:18