@chawuciren
2019-09-29T13:34:50.000000Z
字数 234
阅读 496
CINTA
/*
* Input: integer:x
* Output: x*(1-1/p_1)...(1-1/p_k)
*/
int Euler_phi(int n){
int res=n;
int j=n;
for(int i=2;i<j;i++){
if(n%i==0){
while(n%i==0) n=n/i;//将相同的素因数除去
res=res/i*(i-1);//计算欧拉phi函数
if(n==1) break;//找到所有的素因数以后退出循环
}
}
return res;
}