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: 54ms
Memory: 1744kB
In contest: 1276

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#define clr(a,b) memset(a,b,sizeof(a))
#define ll long long

using namespace std;

const int maxn=1e3+10;
int t,n,ans;
int vis[maxn];

int isprime(int x)
{
	if(x%2==0)return 0;
	for(int i=3;i<=sqrt(x*1.0);i++)
	{
		if(x%i==0)return 0;
	}
	return 1;
}

int main()
{
	scanf("%d",&t);
	vis[2]=1;
	for(int i=3;i<=1000;i++)
	{
		if(isprime(i))vis[i]=vis[i-1]+1;
		else vis[i]=vis[i-1];
	}
	while(t--)
	{
		scanf("%d",&n);
		printf("%d\n",vis[n]);
	}
}