成都X02 第二次IOI 素数密度
2023-08-12 21:09:51
发布于：江苏
0阅读
0回复
0点赞
前言：这次考试我看了眼题目，还是很有难度的，这道题考的是素数筛，当然时间复杂度方面还需要优化
主要考验大家真实的能力，大家看见成绩后也不要太气馁
下面是题解
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){
if(n==1) return false;
else{
for(int i=2;i<=sqrt(n);i++){
if(n%i==0) return false;
}
}
return true;
}
int main(){
int n,q;
cin>>n>>q;
int list[n+1];
for(int i=1;i<=n;i++){
if(isprime(i)) list[i]=1;
else list[i]=0;
}
int arr[n+1]={0};
arr[1]=0;
for(int i=2;i<=n;i++){
if(list[i]) arr[i]=arr[i-1]+1;
else arr[i]=arr[i-1];
}
//for(int i=1;i<=n;i++) cout<<arr[i]<<endl;
//for(int i=1;i<=n;i++) cout<<list[i]<<endl;
int li[q]={0};
for(int i=0;i<q;i++){
int x,y;
cin>>x>>y;
li[i]=arr[n]-arr[x-1]-(arr[n]-arr[y]);
}
for(int i=0;i<q;i++){
cout<<li[i]<<endl;
}
return 0;
}
有帮助，赞一个