HDU1286 找新朋友

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 36000
 4 int m[MAXN];
 5 bool f[MAXN];
 6 int solve(int n){
 7     if(m[n]) return m[n];
 8     int i,j,ans=1;
 9     memset(f,true,sizeof(f));
10     for(i=2;i<n;++i){
11         if(f[i]){
12             if(n%i==0)
13                 for(j=i<<1;j<n;j+=i)
14                     f[j]=false;
15             else ++ans;
16         }
17     }
18     return (m[n]=ans);
19 }
20 int main(){
21     int t,n;
22     memset(m,0,sizeof(m));
23     scanf("%d",&t);
24     while(t--){
25         scanf("%d",&n);
26         printf("%d\n",solve(n));
27     }
28     return 0;
29 }