http://acm.hdu.edu.cn/showproblem.php?pid=1787
模板，就是还有点蒙
#include<stdio.h> #include<math.h> int gcd(int n)//这里可以直接利用欧拉函数的性质：小于n并与n互质的数的个数 { int i,j,ans=n; for(i=2;i<=sqrt(n);i++)//i的范围是这些，判断n是否是质数时就是判断到sqrt（n）就可以。这里跳出循环可以判断n已经是1或者质数了 if(n%i==0) { ans=ans/i*(i-1); while(n%i==0)n/=i;//这里可以保证i一定会是素数，因为下次出现i的倍数的时候不会进去这个循环 } if(n>1)ans=ans/n*(n-1);//有可能除到最后 本身还是一个质因子 return ans; } int main() { int n; while(scanf("%d",&n),n) printf("%d ",n-1-gcd(n)); return 0; }