欧拉函数求n的互质数个数(零基础也能看懂)

质数:质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

欧拉函数:在数论中，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数，或是欧拉总计函数。

公式：φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pk) 其中，n 是一个正整数，p1, p2, …, pk 是 n 的质因子（即 n 的所有不同的质因数），而 k 是质因数的个数。 质因子: 质因子是一个正整数的因数中，指的是质数因子，即只能被 1 和自身整除的因数。换句话说，质因子是指那些不能再分解成更小的因数的因子。例如，15 的质因子有 3 和 5，因为 3 和 5 都是质数，且它们都是 15 的因数，同时也不能再被进一步分解成更小的因数。 这个公式适用于任意正整数 n 的欧拉函数计算，其中 p1, p2, …, pk 是 n 的所有不同的质因数。 这个公式通过将 n 分解为质因数的乘积，然后根据每个质因数的贡献来计算 φ(n)。 φ(15)=15*(1-1/3)*(1-1/5)=8 1、2、4、7、8、11、13、14

欧拉函数的一些性质 1、互素性质： 如果两个正整数 m 和 n 互质（即它们的最大公约数为 1），则有 φ(m*n) = φ(m) * φ(n)。

例如3和5互质φ(3)=2，φ(5)=4 φ(15)=2*4=8

2、素数性质： 对于任意素数 a，有 φ(a) = a - 1。因为素数只有 1 与其本身互质，所以与素数 a 互质的数的个数为 a - 1。例如上述例子3和5

3、幂次性质： 如果 p 是一个质数，而 k 是一个正整数，则有φ(p^k )=p^(k-1) (p-1)这是因为 p^k 以外的数中，有 p^(k-1) 个数与 p^k 互质。这个公式适用于形如 p^k 的素数幂的欧拉函数计算，其中 p 是质数，k 是大于等于 1 的整数。 例 φ(8)=φ(2^3)=4

通过小学分式转换改成result = result // i * (i - 1)

时间复杂度为:O(sqrt(n))

空间复杂度为:O(1)

定义函数euler_phi (n) 求n的互为质数个数

在函数内部，我们首先初始化了变量 result 和 a，它们都被赋值为输入的正整数 n。其中，result 用于存储欧拉函数的结果，而 a 则是一个临时变量，它会在后续过程中被不断处理为 i 的因子。

然后，我们使用一个 for 循环来遍历从 2 到 int(a**0.5) + 1（a 的平方根取整加 1）之间的所有整数 i。这样的范围足以覆盖 a 的所有可能的质因子。在循环中，我们检查当前的 i 是否是 a 的质因子。

如果 a 能够被 i 整除，那么说明 i 是 a 的一个质因子。根据公式（φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pk)），我们首先将 result 除以 i，然后乘以 i-1，接着，我们将 a 除以 i，并持续除以 i 直到 a 不再能整除 i。a这样做的原因是，我们就处理完了当前的质因子 i。

重复以上过程，直到 i 遍历到 int(a**0.5) + 1 结束循环。

如果在循环结束后，a 仍然大于 1，说明 a 还剩余着一个大于 sqrt(a) 的质因子，我们将 result 除以 a，然后乘以 a-1，以处理这个质因子。

最后，我们返回 result，它就是给定正整数 n 的欧拉函数值。

关于范围为什么是int(a0.5) + 1** 这个涉及到质数的定义以及质因数分解的性质。

质数： 质数是指只能被 1 和自身整除的整数，且大于 1。比如，2、3、5、7 等都是质数。

质因数分解的性质： 任意一个大于 1 的整数，都可以被唯一地分解为若干个质数的乘积。这个过程就是质因数分解。例如，12 可以分解为 2 * 2 * 3，其中的 2 和 3 就是 12 的质因数。

基于以上两个性质，可以得出结论：

如果一个整数 a 是一个质数，那么它的质因数只有它自己。因此，它的最大质因数就是它自己，不会超过其平方根。 如果一个整数 a 不是质数，那么它可以分解为若干个质数的乘积。其中的最大质因数一定不会超过 a 的平方根，否则就会产生一个比 a 更小的整数，其平方将大于 a，这与 a 的定义矛盾。 因此，任意整数 a 的最大质因数不会超过其平方根。这一性质使得在质因数分解时，我们只需要考虑从 2 到 a 的平方根（包括平方根本身）的所有可能的因子即可。

假设我们有一个整数 a = 100。我们想要找到它的所有质因数。

首先，我们知道 100 可以分解为以下质因数的乘积：2×2×5×5 其中，最大的质因数是 5。我们可以发现，即使我们继续找到更多的因子，例如 100 的因子有 2、4、5、10、20、25、50、100，但是它们都可以由 2 和 5 的组合得到，而这些因子的最大质因数也不会超过 5。

同样地，如果我们考虑一个更大的整数，比如 10000，它的质因数分解是 2×2×2×2×5×5×5×5，其中最大的质因数是 5。

这个规律适用于任意整数 a。因为我们可以将 a 分解为一系列质数的乘积，而其中最大的质数不会超过 a 的平方根。因此，任意整数 a 的最大质因数不会超过其平方根。

质因子与因子 质因子（Prime Factor）是指一个数中能够被整除的质数因子。而因子（Factor）是指能够整除给定数的整数。

质因子和因子之间存在一定的关系：

一个数的质因子是该数的因子，并且其中的质因子可能包含重复。

一个数的因子可能包含了所有的质因子，也可能只包含其中的一部分，因此质因子是因子的一种特殊情况。

举例来说，考虑数 12：

12 的质因子是 2 和 3，因此 2 和 3 都是 12 的因子。 12 的因子包括 1、2、3、4、6 和 12，其中 2 和 3 是质因子，而其他的因子是由 2 和 3 组合而成的。 因此，质因子是因子的一部分，它们之间是有关联的，但并不完全等同。

本文如有错误，望请指正!