蓝桥杯第十一届国赛Python组试题C阶乘约数——唯一分解定理的应用

• 试题 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)