C语言实现欧拉函数

C语言实现欧拉函数

int eular(int n)
{
//用欧拉公式:k=N*(1/p1)*(p1-1)*(1/p2)(p2-1)……
//其中p1，p2……是N的质因数，不重复计算
//例如100=2X2X5X5，只算p1=2,p2=5，重复的不算
int ret=1,i; //ret是指第二部分（px-1）
for(i=2;i*i<=n;i++)//遍历n以内的质因数
{
if(n%i==0)//如果是质因数
{
n/=i,ret*=i-1;//通过n/px来表示每个质因数第一部分
while(n%i==0) n/=i,ret*=i;//如果重复计算了，就把多除的px乘到ret部分
}
}
if(n>1) ret*=n-1;//最后把两部分相乘合并
return ret;
}

int eular(int n)
{
int ret=1,i; //定义变量
for(i=2;i*i<=n;i++) //从i=2开始循环，判定条件为i*i小于等于n，循环一次i增加1
if(n%i==0) //判定条件为n除以i的余数等于0
{
n/=i,ret*=i-1; //n=n/i，ret = ret*(i-1)
while(n%i==0) //当n除以i的余数等于0时执行下面的语句，否则跳过
n/=i,ret*=i;
}
if(n>1) //如果n>1执行下面语句，否则跳过
ret*=n-1; //ret = ret*(n-1)
return ret;
}

直接复制的百度百科的，没具体看是什么功能