1 #include <iostream> 2 #include <string.h> 3 #include <string> 4 #include <fstream> 5 #include <algorithm> 6 #include <stdio.h> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <cmath> 11 using namespace std; 12 const double eps = 1e-8; 13 const double pi=acos(-1.0); 14 const int INF=0x7fffffff; 15 unsigned long long uINF = ~0LL; 16 #define MAXN 1007 17 #define mod 1000000007 18 typedef long long LL; 19 int s[1000003]; 20 int check(int x) 21 { 22 for(int i=3;i*i<=x;i+=2) 23 { 24 if(x%i==0)return 0; 25 } 26 return 1; 27 } 28 void init() 29 { 30 s[0]=0;s[1]=0;int temp=7; 31 for(int i=2;i<=1000000;i+=2) 32 { 33 temp+=6; 34 s[i+1]=s[i]=s[i-1]+check(temp); 35 } 36 } 37 int main() 38 { 39 int T,n; 40 //freopen("0.in","r",stdin); 41 init(); 42 scanf("%d",&T); 43 while(T--) 44 { 45 scanf("%d",&n); 46 printf("%d ",s[n]); 47 } 48 49 return 0; 50 }
素数~