虽然感觉挺简单，但是还是写个模板吧
n^(0.5)求一次欧拉函数模板
//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和 int phi(int x) { int sum=x; for(int i=2;i*i<=x;i++) { if(x%i==0) { sum=sum-sum/i; while(x%i==0) x/=i; } } if(x!=1) sum=sum-sum/x; return sum; }
原文：http://www.cnblogs.com/chenhuan001/p/5026490.html