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: 1128kB
In contest: 1276

#include<stdio.h>
int A[10000] ={0};
int sushu(int n){
	int i,j,s=0;
	int f=0;
	A[1]=1;
	A[2]=1;
	A[3]=2;
	if(A[n]==0){
		
		 for(i=2;i<=n/2;++i){
			if(n%i==0){
				f=1;
				break;}
		}
		if(f==0)
			s+=1;
		A[n]=sushu(n-1)+s;
	}
	return A[n];
}
int main(void){
	long t;
	int n;
	int s;
	scanf("%ld",&t);
	while(t--){
		
		scanf("%d",&n);
		s=sushu(n);	
		printf("%d\n",s);
	}
	return 0;
}