没错是的，又是模板题。 题源不明。 欧拉函数的定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。 /a与b互质就是gcd(a,b)=1 φ(1)=1， φ(2)=1， φ(3)=2， φ(4)=2， φ(5)=4， φ(6)=2， φ(7)=6， φ(8)=4 易知 素数的欧拉函数的值为 素数-1；
p为素因子即n%p==0；故很容易写出以下代码。
#include<iostream> using namespace std; int main() { int n; while(cin>>n) { if(n==0) break; int rea=n; for(int i = 2 ; i*i<=n;i++) ///大于sqrt(n)的素因子最多有一个故只需最后特判一下 { if(n%i==0){ rea = rea-rea/i; ///欧拉，欧拉，欧拉。 do{ n/=i; ///找到下一个素因子 }while(n%i==0); } } if(n>1) rea = rea -rea/n; ///特判 cout<<rea<<endl; } return 0; }