关于欧拉函数实现中for循环使用i*i ≤n的疑问

首先得说清楚：用i <= n其实能得到正确结果，但问题是效率会低得离谱，这就是为什么我们要换成i*i <=n的核心原因。

咱们结合你这段欧拉函数的代码来拆解：

• 欧拉函数的计算核心是找到n的所有不同质因数，然后套用公式φ(n) = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pk)（p1到pk是n的质因数）。
• 代码里每次找到一个能整除n的i，都会用while循环把n里所有的i因子都除干净——这意味着后面的循环里，i的倍数根本不会再被选中，因为n已经没有i这个因子了。

那为什么i*i <=n就足够覆盖所有需要找的质因数呢？
这是数论里的一个小结论：一个数n的所有质因数，要么是小于等于√n的，要么是大于√n的（而且这种大于√n的质因数最多只能有一个——要是有两个的话，它们的乘积肯定会大于n，这就矛盾了）。

所以当循环条件到i*i >n时，剩下的n如果还大于1，那它本身就是那个唯一的大于√n的质因数，这也就是代码最后那个if(n>1)分支要处理的情况。

如果换成i <=n会怎么样？
就拿你代码里的n=36来说，当i循环到6的时候，n已经被除到1了（因为代码里把所有2和3的因子都清掉了），后面i从7到36的所有循环都是白跑的，完全不会触发任何逻辑，纯纯浪费计算资源。要是n是个很大的数，比如1e6，用i*i <=n最多循环1000次，用i <=n要跑1e6次，这效率差距简直是天壤之别。

总结一下：i*i <=n是质因数分解（包括欧拉函数计算）里的标准效率优化，既不影响结果正确性，又能砍掉绝大多数无效循环，尤其是n越大，优化效果越明显。

内容来源于stack exchange