首先介绍下欧拉函数的定义：
欧拉函数，又称为“φ函数”，表示小于等于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。
希望上面的解释能够帮到你。
本站部分内容来源互联网,如果有图片或者内容侵犯了您的权益，请联系我们，我们会在确认后第一时间进行删除！