aret

userId_undefined

最强用户

倔强青铜

2024-08-07 11:06:28

发布于：广东

0阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],pre[N],n,q;
void init(int n){
    a[1]=1;
    for(int i=2;i*i<=n;i++){
        if(a[i]==0){
            for(int j=i+i;j<=n;j+=i){
                a[j]=1;
            }
        }
    }
}


int main() {
    freopen("shu.in", "r", stdin);
    freopen("shu.out", "w", stdout);
    cin>>n>>q;
    init(n);
    for(int i=1;i<=n;i++){
        if(a[i]==0)
            pre[i]=pre[i-1]+1;
        else
            pre[i]=pre[i-1]+0;
    }
    while(q--){
        int L,R;
        cin>>L>>R;
        cout<<pre[R]-pre[L-1]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论