计算Euler's Phi function
即,输入整数n,求大于等于1,小于n且与n互素的整数个数。这是大二CINTA课的作业。
第一种做法,利用gcd函数(总该知道为什么gcd要返回值而不是printf输出了吧?),比较常规
int phi(unsigned int n)
{
unsigned int result = 1; //至少有一个1满足要求;
for (int i = 2; i < n; i++) //所以循环从2开始,到n-1结束
if (gcd(i, n) == 1) //i与n互素
result++;
return result;
}
第二种做法,分解n
int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
请大家自行验证一下。并分析,第一种方法与第二种方法相比,效率上有多大差别?