C+解法

#include<iostream>
using namespace std;
bool prime(int n)
{
    int i;
    if(n>1)
    {
        for(i=2;i*i<=n;i++)
            if(n%i==0)
                return 0;
        return 1;
    }
    return 0;
}
int main()
{
    long t,i,n;
    int a[1000001];
    a[0]=0;
    a[1]=0;
        for(i=2;i<=1000000;i++)
            if(prime(i))
                a[i]=a[i-1]+1;
        else a[i]=a[i-1];
         cin>>t;
        for(i=1;i<=t;i++)
        {
            cin>>n;
            cout<<a[n]<<endl;         }
    return 0;
}