质数数量
本人出师牛,发题解有一点小激动。
这题的主要问题是——超时!!!
解决方法为——递推!!!
和其他题目一样,我们先来找规律。
//我们知道不大于0的质数有0个,所以: f[0]=0; if(用f[n]来表示不大于n的质数个数&&n>0){ f[1]=0; f[2]=1; f[3]=2; f[4]=2; f[5]=3; f[6]=3; f[7]=4; ... } //我们会发现: //如果n不是质数,不大于n的质数数量就等于不大于n-1的质数数量, //反之,不仅要算不大于n-1的质数数量,还要算上自己。 //所以: if(n>0){ if(n是质数) f[n]=f[n-1]+1; else f[n]=f[n-1]; }
是不是有一点思路了呀?
所以,我们只要按这个规律把所有的数据算出来,然后直接输出就可以了(注意不是打表!)。
代码如下:
#include<iostream> #include<cmath> using namespace std; int f[1000001];//用于存储答案 bool Prime(int n){//判断质数 int i; if(n>1){ for(i=2;i<=floor(sqrt(n));i++) if(n%i==0) return false; return true; } return false; } int main(){ int i,t,n; f[0]=0; f[1]=0; cin>>t; for(i=2;i<=1000000;i++) f[i]=Prime(i)==true? f[i-1]+1:f[i-1];//算出所有的答案(递推核心) for(i=1;i<=t;i++){ cin>>n; cout<<f[n]<<endl;//直接输出 } return 0; }
感觉像上了一节课,请问我讲明白了吗?
if(我讲明白了) 点赞; else 在评论区问我;