质数数量

本人出师牛，发题解有一点小激动。
这题的主要问题是——超时！！！
解决方法为——递推！！！
和其他题目一样，我们先来找规律。

//我们知道不大于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 在评论区问我;