java - 解释Euler's Totient Implementation的实现

Question

我在一个编码平台上看到这段代码可以有效地计算不同值的欧拉 totient。 我无法理解这个实现。我真的很想学这个。谁能帮我解释一下？

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}

Answer 1

首先，让我们注意对于质数 p，phi(p) = p - 1。这应该是相当直观的，因为所有小于质数的数字都必须与所述质数互质。那么我们开始进入我们的外部 for 循环:

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;

这里我们将i的值添加到phi(i)。对于主要情况，这意味着我们需要预先使 phi(i) 等于 -1，并且必须调整所有其他 phi(i)进一步考虑互质整数的数量。关注主要情况，让我们说服自己这些确实等于 -1。

如果我们单步执行循环，在 i=1 的情况下，我们最终将遍历内部循环中的所有其他元素，减去 1。

   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }

要减去任何其他值，j 必须等于素数 p。但这需要 j = 2 * i + i * k 等于 p，对于某些迭代 k。这不可能，因为 2 * i + i * k == i * (2 + k) 暗示 p 可以被 i，它不能(因为它的主要部分)。因此，所有 phi(p) = p - 1。

对于非素数i，我们需要减去互素整数的个数。我们在内部 for 循环中执行此操作。重复使用之前的公式，如果 i 除以 j，我们得到 j/i = (2 + k)。所以每个小于 i 的值都可以乘以 (2 + k) 以小于 j，但有一个公因数 (2 + k) 与 j(因此，不是互质)。

但是，如果我们减去包含 (2 + k) 因子的 (i - 1) 倍数，我们将多次计算相同的因子。相反，我们只计算与 i 互质的那些，或者换句话说 phi(i)。因此，我们剩下 phi(x) = x - phi(factor_a) - phi(factor_b) ... 来解释所有 (2 + k_factor) 倍数小于所述因子的互质数，现在与 x 共享一个因子 (2 + k_factor)。

将其放入代码中可以为我们提供上述内容:

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}