牛客竞赛 质数数量
质数数量题目
https://ac.nowcoder.com/acm/problem/22226
这道题我第一次提交用的是普通的计算质数的做法，可是：答案都错误啊 （代码如下）
#include
using namespace std;
bool sushu(int n){for(int i=2;i<=sqrt(n);i++){if(n%i==0){return false;}}if(n<=1) return false;return true;
}
int n,c;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>x;for(int j=1;j<=x;j++){if(sushu(j)) c++;}cout< 我看了看题目，我觉得这题的数据范围太大了，都10^6了！！！
所以，在我的代码里加了一些修改：
首先，判断质数的函数要改那么一点点，用一个变量flag来标记这个数是否是质数，如果是质数，返回1，如果不是质数，返回0，改了的判断质数的代码：
int prime(int n){//判断是否是质数的函数int flag=0;if(n==1){//判断特殊情况return 0;}for(int i=2;i<=sqrt(n);i++){if(n%i==0){//不是质数的情况flag=1;//标记为1 break;}}if(flag==1){//不是质数return 0;}else{//是质数return 1;}
}接下来就要改改主函数了！！！
首先，定义一个a数组，这个数组就是用来输出质数个数的！
然后，将a数组的一些边界写好：
a[0]=0;//从1~0的质数个数为0
a[1]=0;//从1~1的质数个数为1写好之后，就要做一些正经的不是边界的事情了。
因为直接判断会超时，所以我们这样做：
判断：
1、如果这个数是质数，那么我们就取前面数的a数组里的值+1（因为是质数，所以指数的数量又多了一个，也就是+1）。
2、如果这个数不是质数，那么我们就取前面数的a数组里的值。
for(int i=2;i<=1000000;i++){if(prime(i)){a[i]=a[i-1]+1;}else{a[i]=a[i-1];}
}然后就是一些普通的输入+输出：
int t;
cin>>t;
while(t--){int n;cin>>n;cout<就是做这些修改，这道题就AC了。
贴代码：
#include
using namespace std;
int a[1000010];
int prime(int n){int flag=0;if(n==1){return 0;}for(int i=2;i<=sqrt(n);i++){if(n%i==0){flag=1;break;}}if(flag==1){return 0;}else{return 1;}
}
int main(){a[0]=0;a[1]=0;for(int i=2;i<=1000000;i++){if(prime(i)){a[i]=a[i-1]+1;}else{a[i]=a[i-1];}}int t;cin>>t;while(t--){int n;cin>>n;cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！