题解 | #质数数量#

这一题很多人的问题可能会在于时间，用传统的循环做，时间复杂度会很大，对于每一个给定的数字，都要从2~n去遍历，实际上会有很多重复操作，与其这样，不如一开始就将1000000之内的质数找出来，保存到一个数组中，这样对于每一个给定的数字，就可以直接输出他的质数和。

#include<stdio.h>
#include<math.h>//包含sqrt平方函数；
int main ()
{
    int T,n=0,i,flag,j;
    int number[1000001]={0};//定义一个数组来储存
    for( j=2;j<1000001;j++){
        flag=1;//一个标识
        for(i=2;i<=(int)sqrt(j);i++)//判读一个数是否为质数，只需要判读2~sqrt(n)内是否有能整除的数
        {
            if(j%i==0)
            {
                flag=0;
                break;
            }
        }
        if(flag==1)//当flag==1；说明没有进入到if判断中，这个数为质数
        {
            n++;当前数内有多少个质数
        }
        number[j]=n; 将n保存到数组中，为j所对应的质数的多少；
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",number[n]);
    }
    return 0;
}