HDU 1286 找新朋友

思路：用欧拉函数找与N互质数的数量

[cpp]
#include<iostream> 
#include<cstdio> 
using namespace std; 
const int N=32770; 
int prime[N],phi[N]; 
bool a[N]; 
void is_prime() 
{ 
    int i,j,k; 
    k=0; 
    for(i=2;i<N;i++) 
    { 
       if(!a[i]) 
       {  
          prime[k++]=i; 
          phi[i]=i-1; 
       } 
       for(j=0;j<k&&i*prime[j]<N;j++) 
       { 
          a[prime[j]*i]=1; 
          if(i%prime[j]) 
              phi[i*prime[j]]=phi[i]*(prime[j]-1); 
          else 
          { 
             phi[i*prime[j]]=phi[i]*prime[j]; 
             break; 
          } 
       } 
    } 
} 
int main() 
{ 
    int T,n; 
    is_prime(); 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d",&n); 
      printf("%d\n",phi[n]); 
    } 
   return 0; 
} 

补充：软件开发 , C++ ,

上一个：不使用man 3 printf的函数，实现一个简单的printf函数
下一个：hdu4282 A very hard mathematic problem-----天津网络赛