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: 65ms
Memory: 1116kB
In contest: 1276

#include<stdio.h>
#include<math.h>
int isPrime(int a){
	int i,flag;
	flag=0;
	if(a==2){
		return 1;
	}
	if(a%2==0){
		return 0;
	}
	for(i=3;i<=sqrt(a);i=i+2){
		if(a%i==0){
			flag=i;
		}
	}
	if(flag==0){
		return 1;
	} else {
		return 0;
	}
}
int main()
{
	int T,i,n,k;
	scanf("%d",&T);
	while(T--){
		int num=0;
		scanf("%d",&n);
		if(n<200){
			k=2;
			num=0;
		} else  if(n<400){
			k=200;
			num=46;
		} else if(n<600){
			k=400;
			num=78;
		} else if(n<800){
			k=600;
			num=109;
		} else if(n<1000){
			k=800;
			num=139;
		} else {
			k=1000;
			num=168;
		}
		for(i=k;i<=n;i++){
			if(isPrime(i)==1){
				num++;
			}
		}
		printf("%d\n",num);
	}
	return 0;
	
}