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: 53ms
Memory: 1120kB
In contest: 1276

#include <stdio.h>
#include <math.h>

int arr[1001];

int isp(int n) {
  int i, l, f = 1;
  if(n <= 1) {
  	f = 0;
  }else if(n == 2) {
  	f = 1;
  }else if(n % 2 == 0) {
  	f = 0;
  }else {
  	l = sqrt(n) + 1;
  	for (i = 3;i <= l; i += 2) {
  	  if(n % i == 0) {
  	    f = 0;
		break;	
	  }	
	}
  }
  return f;
}
int main() {
	int T, n, sum = 1, r;
	for(int i = 3;i <= 1000;i +=2) {
		if(isp(i) != 0) {
		   sum ++;
		   arr[i - 1] = sum;
//		   printf("%d %d\n", arr[i - 1], i);
		}else {
		   arr[i - 1] = 0;
		}
	}
	scanf("%d", &T);
	while(T --) {
	  scanf("%d", &n);
	  r = 0;
	  for(int i = n - 1;i >= 2; i --){
	  	if(arr[i]) {
	  	  r = arr[i];
			break;	
		}
	  }
	  if(n == 2) {
	  	 printf("1\n");
	  }else {
	     printf("%d\n", r);	  	
	  }

	}
	return 0;
}