看不懂欧拉函数
Unable to understand Euler totient function
我是通过下面的Euler-totient函数的实现来的
int fi(int n) {
int result = n;
for(int i=2;i*i <= n;i++) {
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}
我无法理解以下结果陈述的目的
result -= result / i;
result -= result / n;
声明:
result -= result / i;
等于:
result -= (result / i);
等于:
quotient = result / i;
result -= quotient;
等于:
quotient = result / i;
result = result - quotient;
第二种说法很相似
我是通过下面的Euler-totient函数的实现来的
int fi(int n) {
int result = n;
for(int i=2;i*i <= n;i++) {
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}
我无法理解以下结果陈述的目的
result -= result / i;
result -= result / n;
声明:
result -= result / i;
等于:
result -= (result / i);
等于:
quotient = result / i;
result -= quotient;
等于:
quotient = result / i;
result = result - quotient;
第二种说法很相似