prime可以这样写
```cpp
bool prime(int a)
{
bool flag=true;
if(a==1) return false;
else
{
for(int j=2;j<=sqrt(a);j++)
{
if(a%j==0)
{
flag=false;
break;
}
else continue;
}
if (flag||a==2||a==3) return true;
else return false;
}
}
```
by Liboy53_I_HATE_MATH @ 2024-04-06 13:39:56
@[Ice_rnfmabj](/user/695943)
by Liboy53_I_HATE_MATH @ 2024-04-06 13:58:43
@[Ice_rnfmabj](/user/695943)
线性筛+前缀和
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
long long pd[N],zs[N],top,sum[N],n,l,r;
void xxs(long long i)
{
for(int j=2;j<=i;++j)
{
if(!pd[j]) ++top,zs[top]=i;
for(int z=1;zs[z]*i<=N;++z)
{
pd[zs[z]*i]=1;
if(i%zs[z]==0)
break;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
xxs(N-5);
for(int i=1;i<=N-5;++i)
sum[i]=sum[i-1]+(pd[j]^1);
cin>>n;
while(n--)
{
cin>>l>>r;
cout<<sum[r]-sum[l-1]<<'\n';
}
return 0;
}
by Yesod @ 2024-04-06 15:37:21
@[Yesod](/user/754321)
在刚才我自己写了一个，但是输入输不进去了。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5*1e6;
int prime[N],cnt,s[N+10],x;
bool st[N];
void xxsq(long long n){
for(int i=2;i<=n;i++){
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++){
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
for(int i=0;i<=N;i++){
s[i]=s[i-1]+(!st[i]);
}
}
int main(){
cin>>x;
xxsq(N);
while(x--){
long long l,r;
cin>>l>>r;
cout<<s[r]-s[l]<<"\n";
}
return 0;
}
```
by Ice_rnfmabj @ 2024-04-06 15:47:23
我成乐子了
我刚没看出来我的代码和原来一模一样（逃
by Liboy53_I_HATE_MATH @ 2024-04-06 15:51:38
@[Ice_rnfmabj](/user/695943)
我这边测试你那个代码是没有问题的
~~我现在发现我之前写的代码有些锅~~
by Yesod @ 2024-04-06 16:01:10
扔一个样例：
样例输入
```
3
1 5
4 10
7 13
```
样例输出
```
3
2
3
```
by Ice_rnfmabj @ 2024-04-06 17:10:18
@[Yesod](/user/754321) 谢特，是我那个奇妙编译器的问题。
我那个在```7 13```那组会输出```2```
by Ice_rnfmabj @ 2024-04-06 17:13:51
@[Ice_rnfmabj](/user/695943)
第一不是 $ s_r-s_l $ 是 $ s_r-s_{l-1} $
第二 $ 1 $ 不是质数，我上面代码没特判
by Yesod @ 2024-04-06 17:26:03
@[Yesod](/user/754321) 改好了，已过，thx！
by Ice_rnfmabj @ 2024-04-06 17:31:15