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;
}
我看到了上面的Euler phi函数实现,它是O(sqrt n)级别的。我不理解为什么在for循环中要使用i*i<=n和改变n的原因。据说可以在远小于O(sqrt n)的时间内完成。如何实现呢?链接(俄语)