Python 实现：计算 n! 不同因子个数，附代码详解与复杂度分析

以下是使用Python实现计算 `n!` 不同因子个数的代码： ```python # 该函数用于对一个数进行质因数分解并统计每个质因数的指数 def prime_factorize(num, prime_count): # 从2开始遍历到该数的平方根 divisor = 2 while divisor * divisor <= num: while num % divisor == 0: # 如果该质因数已经在字典中，将其指数加1 if divisor in prime_count: prime_count[divisor] += 1 else: # 若不在字典中，将其添加到字典并将指数设为1 prime_count[divisor] = 1 num //= divisor divisor += 1 # 如果最后剩余的数大于1，说明它本身是一个质因数 if num > 1: if num in prime_count: prime_count[num] += 1 else: prime_count[num] = 1 # 该函数用于计算 n! 的不同因子个数 def count_factors(n): prime_count = {} # 对从2到n的每个数进行质因数分解 for i in range(2, n + 1): prime_factorize(i, prime_count) factor_count = 1 # 根据质因数指数计算因子个数 for exponent in prime_count.values(): factor_count *= (exponent + 1) return factor_count # 读取输入的整数n n = int(input()) # 计算并输出 n! 的不同因子个数 print(count_factors(n)) ``` 代码说明： 1. `prime_factorize` 函数：该函数用于对一个数进行质因数分解，并统计每个质因数的指数。它会遍历从2到该数平方根的所有数，将能整除该数的质因数及其指数记录在字典 `prime_count` 中。 2. `count_factors` 函数：该函数会对从2到 `n` 的每个数调用 `prime_factorize` 函数进行质因数分解，统计所有质因数的指数。然后根据公式：如果一个数可以表示为 $p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$（其中 $p_i$ 是质因数，$a_i$ 是其指数），那么它的因子个数为 $(a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$，计算并返回 `n!` 的不同因子个数。 3. 主程序：读取输入的整数 `n`，调用 `count_factors` 函数计算并输出 `n!` 的不同因子个数。 复杂度分析： - 时间复杂度：$O(n\sqrt{n})$，其中 $n$ 是输入的整数。因为对每个从2到 $n$ 的数都要进行质因数分解，而质因数分解的时间复杂度是 $O(\sqrt{n})$。 - 空间复杂度：$O(k)$，其中 $k$ 是 `n!` 的不同质因数的个数。主要用于存储质因数及其指数的字典。 ######[AI问答 | 731点数解答 | 2026-01-12 12:15:34]