Start: Jun, 28, 2019 08:42:00
2019杭州师范大学第一届程序设计竞赛新生赛
End: Jun, 28, 2019 11:42:00
Time elapsed:
Time remaining:

Problem_ID: F
Result: Accepted
Time: 59ms
Memory: 2592kB
In contest: 1276

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
#define maxn 100010
#define ll long long
#define mm(a,b) memset(a,b,sizeof(a))
int prime[maxn];
int sum[maxn];
bool isp[maxn];
void f()
{
	mm(isp,true);
	int sq=sqrt(double(maxn))+1;
	int i,j,k;
	for(i=2;i<sq;++i)
	{
		if(isp[i])
		{
			for(j=2;j<maxn/i+1;++j)
				isp[j*i]=false;
		}
	}
	isp[0]=isp[1]=false;
	for(int i=2;i<maxn;++i)
		sum[i]=sum[i-1]+isp[i];
}
int main(){
	int n,x;
	cin>>n;
	f();
	while(n--)
	{
		scanf("%d",&x);
		printf("%d\n",sum[x]);
	}
}