时间戳

首页 > 解决方案 > 讲解Euler's Totient Implementation的实现

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

问题描述

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

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

标签： javaalgorithmmath

解决方案

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

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

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

如果我们单步执行循环，在 case 处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)小于，但与 jj有一个公因数（因此，不是互质的）。(2 + k)

但是，如果我们减去(i - 1)包含(2 + k)因子的倍数，我们会多次计算相同的因子。相反，我们只计算那些与 互质的i，或者换句话说phi(i)。因此，我们phi(x) = x - phi(factor_a) - phi(factor_b) ...需要考虑(2 + k_factor)小于所述因子的所有互质数的倍数，它们现在共享一个因子(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]; 
   }
}

推荐阅读