计算 phi(k) 的总和（1 <= k <= N）？

Question

我需要计算 1 <= k <= N 的 phi(k) 总和，其中 N = 1,000,000 且 phi(k) 是欧拉 totient 函数。这是一个项目欧拉问题。我已经使用之前的StackOverflow 问题解决了这个问题，它要求计算 phi(k) 的每个值（1 < k < N）。但是，我想知道是否可以进行任何进一步的优化，因为我们只需要最终的总和phi(k) 而不是每个加数的单独值。

Answer 1

关于 Euler's totient 函数的维基百科页面包含Arnold Wafisz 提出的一个公式，用于计算从 1 到 n 的 k 的 φ(k) 之和：

\n\n

sum(1<=k<=n) \xcf\x86(k) = (1 + sum(1<=k<=n) \xce\xbc(k)*(floor(n/k))^2) / 2\n

\n\n

（在维基百科上阅读要容易得多。）

\n\n

如果k具有任何平方素因数，则 M\xc3\xb6bius 函数 μ( k ) 为 0，否则为 (-1) f ，其中f^是k中唯一素因数的数量。（换句话说，如果k的素数分解有偶数个唯一素数，则为 1；如果有奇数个，则为 -1；如果某个素数出现多次，则为 0。）您应该能够使用修改筛法以快速计算 μ( k )。

\n\n

这可能会更快一些。

\n