试题 C: 阶乘约数
问题描述
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
思路
直接求100的阶乘数值之后再求所有的约数的方式不可取，时间需求太大，这里使用唯一分解定理。
唯一分解定理
简而言之就：
用在这里若想求出100！的所有质数所消耗时间也是非常大，这里求出逐个1-100内所有的质数个数，质数个数求和，最后再相乘即可。
题解
def jiechengyueshu2(): # 哈希表 存放质数 temp = {} # 求出100以内所有质数 for i in range(2, 101): judge = True for j in range(2, floor(sqrt(i))+1): if i % j == 0: judge = False if judge: temp[i] = 1 # 求出2-100所有的质数和 for i in range(2, 101): index = i for key in temp.keys(): while index % key == 0: index //= key temp[key] += 1 ans = 1 # print(temp) # 按照唯一分解定理规律，将所有质数之和相乘即可，这里没有每一项都+1，因为哈希表中每一项的初始值为1 for i in temp.values(): ans *= i print(ans)
