http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1136
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n))
p(1) p(2) p(n)是X的质因数
#include<iostream> using namespace std; int main() { int n; cin>>n; int ans=n; for(int i=2;i*i<=n;i++) { if(n%i==0) ans=ans/i*(i-1); while(n%i==0) n/=i; } n>1?cout<<ans/n*(n-1):cout<<ans; return 0; }
最后一个质数没在循环内计算,所以还要在循环外算一次,同时要注意当最后的质数为1时直接输出