题解 | #质数数量#

#include<stdio.h>
#include<math.h>
#define kk 1000001
int main ()
{
    int t=0,n=0;//t个数输入n
    int i=0,j=0,k=0;//循环
    int cnt=0;//标记
    int count=0;//计素数
    int a[kk]={0};
        for(j=2;j<=kk;j++)//数组顺存素数个数
        {
        	cnt=0;//更新标记
            for(k=2;k<=sqrt(j);k++)//开平方减少重复运算
            {
                if(j%k==0)//不是素数
                {
                    cnt=1;
                    break;
                }
            }
            if(cnt==0)//是素数
            {
            	count++;
			} 
			a[j]=count;//n前素数个数存入数组
		}
		scanf("%d",&t);
		for(i=1;i<=t;i++)
		{
			scanf("%d",&n);
			printf("%d\n",a[n]);
		}
    return 0;
}