解释欧拉Totient实现的实现

Question

我已经在编码平台中看到了此代码，可以有效地计算出不同值的欧拉糖度。我无法理解此实现。我真的很想学这个。谁能帮我解释一下吗？

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 的公因数（因此，不是互质）。

但是，如果我们减去(i - 1)包含(2 + k)因子的倍数，则会多次计算相同的因子。取而代之的是，我们仅计算与互质的i或换句话说phi(i)。因此，我们只剩下phi(x) = x - phi(factor_a) - phi(factor_b) ...考虑到所有的(2 + k_factor)coprimes小于上述因数的倍数，现在共享的因素(2 + k_factor)有x。

将其放入代码中，就可以为我们提供您上面完全一样的功能：

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]; 
   }
}