计算euler phi函数

Question

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).我没有得到i*i<=n在for循环中使用的事实并且需要改变.n据说它可以在更小的时间内完成O. (sqrt n)怎么样？链接(俄语)

Answer 1

i*i<=n与i<= sqrt(n)您的迭代仅持续到的顺序相同sqrt(n).

使用Euler totient函数的直接定义,您应该找到分割的素数n.