CINTA作业9-编程题

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;
}