欧拉函数的定义

1~n中与n互质的数的个数称为欧拉函数，记为

例：，，，，

#include<iostream>
using namespace std;int phi(int n){int res=n;for(int i=2;i*i<=n;i++){if(n%i==0){res=res*(i-1)/i;while(n%i==0) n=n/i; }}if(n>1) res=res*(n-1)/n;return res;
}
int main(){int n;cin>>n;cout<<phi(n)<<endl;return 0;
}