Java欧拉函数的计算代码详解

首先介绍下欧拉函数的定义：

首先介绍下欧拉函数的定义：

欧拉函数，又称为“φ函数”，表示小于等于n的正整数中有多少个与n互质。记做φ(n)。

Java中计算欧拉函数的代码如下（假设要计算的数为n）：

public static int eulerFunction(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

这段代码中，我们需要对n的每个质因数i进行操作，res就是最终结果，初始值为n本身，然后对于每个i：

• 如果i是n的质因数，我们需要将res除以i，然后乘上i-1，这是因为对于每个i，该质因数与n的其他质因数都互斥，我们只需要将互斥的质因数个数乘起来即可。同时，我们需要将n变为n/i的值，因为我们已经统计了i这个质因数。
• 如果i不是n的质因数，我们什么都不用做，继续找下一个质因数。

最后，如果n最终仍然大于1，由于n是质因数，所以直接将res除以n，然后乘上n-1即可。

示例1：计算n为10的欧拉函数，即φ(10)。

用上面的代码进行计算，得到res的初始值为10。然后我们发现2是10的一个质因数，于是执行如下操作：

res = res / 2 * (2 - 1);  // res变为5
n = 10 / 2;  // n变为5

接着我们发现3不是10的质因数，继续往下找，发现5是10的质因数，于是执行如下操作：

res = res / 5 * (5 - 1);  // res变为4
n = 5 / 5;  // n变为1

此时n已经为1了，循环结束，最终结果为4，即φ(10)=4。

示例2：计算n为21的欧拉函数，即φ(21)。

用上面的代码进行计算，得到res的初始值为21。然后我们发现2不是21的质因数，于是继续往下找，发现3是21的一个质因数，于是执行如下操作：

res = res / 3 * (3 - 1);  // res变为12
n = 21 / 3;  // n变为7

此时7不是完全平方数，继续往下找，发现7是21的一个质因数，于是执行如下操作：

res = res / 7 * (7 - 1);  // res变为6
n = 7 / 7;  // n变为1

此时n已经为1了，循环结束，最终结果为6，即φ(21)=6。

希望上面的解释能够帮到你。