无符号长整型条件判断未生效，循环未按预期提前终止问题

一、循环终止条件的预期错误 #

你误以为45^5超过了14!的一半，但实际计算数值就能发现问题：

• 14! 的值是 87178291200，它的一半是 43589145600
• 45^5 = 184528125，这个值远小于43589145600
• 45^6 = 8303765625，依然小于43589145600
• 直到45^7 = 373669453125，才会大于43589145600，所以循环会执行到i=7才终止。

你的预期偏差源于对数值大小的误判——45的幂增长虽快，但14!本身的数值量级更大，所以要到7次方才会超过它的一半。

二、代码的低效问题 #

除了预期错误，你的代码还有两处明显的低效点：

1. 重复计算45的幂：每次循环都从1开始乘45，完全可以在上一次的结果基础上直接乘45，比如把x的初始化移到循环外，每次循环执行x *=45即可，不用嵌套循环重新计算。
2. 冗余的终止逻辑：其实不需要等到x超过fact的一半，只要第一次出现fact % x !=0，后续更大的45幂肯定也无法整除fact（因为更大的幂是当前x乘45，当前x都无法整除的话，乘45后只会有更多的质因数，更不可能整除），所以此时直接终止循环即可，能提前结束不必要的计算。

三、更高效的解法思路 #

找最大的p使得45^p整除n!，最合理的方法是质因数分解法：
因为45 = 3² ×5，所以45^p = 3^(2p) ×5^p。要让它整除n!，必须满足：

• n!中质因数3的总个数 ≥ 2p
• n!中质因数5的总个数 ≥ p

只需分别计算n!中3和5的指数：

• 计算5的指数：count5 = n//5 + n//25 + n//125 + ...，直到除数大于n
• 计算3的指数：count3 = n//3 + n//9 + n//27 + ...，直到除数大于n
• 最终p = min(count5, count3//2)

以n=14为例：

• count5 = 14//5 = 2（5和10各贡献一个5）
• count3 = 14//3 +14//9 =4+1=5
• count3//2=2，所以p=min(2,2)=2，和你的程序结果一致。

这个方法不需要计算n!，既避免了大数溢出的风险（当n较大时，n!会超出unsigned long long的范围），又能极大提升计算效率。

内容的提问来源于stack exchange，提问作者dr 21