NC22226. 质数数量
描述
输入描述
第一行输入一个整数T，表示询问的个数
接下来T行每行输入一个整数n.
1<=T<=1e8,1<=n<=1000000
输出描述
对于每个询问n输出小于等于n的的质数的个数。
示例1
输入:
2 10 1000000
输出:
4 78498
C(clang11) 解法, 执行用时: 269ms, 内存消耗: 4296K, 提交时间: 2020-12-01 13:51:29
#include<stdio.h>
int main()
{int a[1000001],i,j,sum=0;
for(i=2;i<1000001;i++)
{for(j=2;j*j<=i;j++)
{if(i%j==0)
{break;}}
if(j*j>i)
{sum++;}
a[i]=sum;}
int t;
scanf("%d",&t);
while(t--)
{int n;
scanf("%d",&n);
printf("%d\n",a[n]);}}