C语言中如何利用质数数组统计n!的质因数出现次数？

核心思路：用Legendre公式直接计算次数 #

不用计算n!，对每个质数p，它在n!里的出现次数可以通过累加以下数值得到：

• 1到n中能被p整除的数的数量（n // p），这些数至少贡献1个p
• 能被p²整除的数的数量（n // p²），这些数额外多贡献1个p
• 继续计算p³、p⁴...直到p的k次方大于n，把所有结果相加就是p的总出现次数

结合质数数组的具体操作步骤 #

1. 先准备好2到99的质数数组（比如[2, 3, 5, 7, 11, ..., 97]）
2. 遍历数组里的每个质数p：
   • 如果p > n，直接跳过（n!里不可能包含比n大的质因数）
   • 初始化计数器count = 0，当前幂次current = p
   • 循环：只要current <= n，就把n // current加到count里，然后current *= p
   • 循环结束后，count就是p在n!中的出现次数
3. 按要求格式输出结果，比如n=5时：
   • 2的次数：5//2 + 5//4 = 2 + 1 = 3
   • 3的次数：5//3 = 1
   • 5的次数：5//5 = 1
     最终输出 5! = (2, 3), (3, 1), (5, 1)

关键细节 #

• 全程都是整数运算，完全不会出现溢出问题，因为n最大是99，每个质数的循环次数最多也就六七次（比如2的7次方是128，已经超过99）
• 只处理数组里小于等于n的质数，效率很高

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