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: 56ms
Memory: 1748kB
In contest: 1276

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int vis[1100];
int sum[1100];
int main (void){
	memset(vis,0,sizeof(vis));
	memset(sum,0,sizeof(sum));
	for(int i=2;i<=1000;i++){
		int flag=1;
		for(int z=2;z<=sqrt((double)i);z++){
			if(i%z==0){
				flag=0;
				break;
			}
		}
		vis[i]=flag;
		//printf("*****%d****%d\n",i,flag);
	}
	for(int i=2;i<=1000;i++){
		sum[i]=vis[i]+sum[i-1];
	}
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%d\n",sum[n]);
	}
	return 0;
}