// http://acm.hdu.edu.cn/showproblem.php?pid=1286 // 这是一个数论问题,求互质的数字有多少个 ////////////////////////////////////////////////////////// // 用素数删选法选出满足条件的 // 法一: // Accepted 1286 156MS 348K 602 B C #include<stdio.h> int peo[32768]; int main() { int i,j,n,t,pos; while(scanf("%d",&t)!=EOF) { while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) peo[i]=1; for(i=2;i<=n;i++) { if(n%i==0) for(j=i;j<=n;j+=i) peo[j]=0; } pos=0; if(n!=1) // 说明不止一个人 for(i=1;i<=n;i++) if(peo[i]) pos++; printf("%d\n",pos); } } return 0; } ////////////////////////////////////////////// // 下面一种利用到欧拉的phi函数 // 法二: // Accepted 1286 15MS 220K 570 B C #include<stdio.h> int phi(int n) // 这个是常见的phi函数模版 { int ans,i,k; if(n==1) ans=0; else { ans=n;k=1; for(i=2;n!=1;i+=k) { if(n%i==0) { ans*=(i-1);ans/=i; while(n%i==0) n/=i; i=k; } } } return ans; } int main() { int n,t; while(scanf("%d",&t)!=EOF) { while(t--) { scanf("%d",&n); printf("%d\n",phi(n)); } } return 0; }