Topic

试题 C: 阶乘约数
本题总分：10 分

##【问题描述】

定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。

##【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

Solution

本题运用到了唯一分解定理
简单来说：

若正整数n可分解为p1^a1*p1a2*…pk^ak
其中pi为两两不同的素数,ai为对应指数，则n的约数个数为(1+a1)(1+a2)…(1+ak)
如180=22335=2^2*325
180的约数个数为(1+2)(1+2)*(1+1)=18个。

一个大于 1 的数不管是质数还是合数一定可以由一个或多个质数乘得。
2: 2; 3: 3; 4: 2 * 2; 5: * 5; 6: 2 * 3; 7: * 7; 8: 2 * 2 * 2; 9: 3 * 3

所以只要将他们每个质数有或没有的所有可能都遍历出来，就是约数的个数了。

仅需求100的阶乘的所有质数遍历出来就是可能了

那么先求100以内的素数（所有可能）
之后我们仅需计算素数出现的次数即可

计算100阶乘需要有1到100的100个数相乘
那么我们在这里成为被乘数

如果我们直接对100的阶乘求出现的素数会很慢
所以我们采用对每个被乘数进行单独计算

对每个被乘数进行因式分解后求出的素数
将其出现的次数记录在dic中

Code

number = 2
data = []
while number < 101:
    prime = True
    i = 2
    while i <= number ** 0.5:
        if number % i == 0:
            prime = False
            break
        else:
            i += 1

    if prime:
        data.append(number)
        number += 1
    else:
        number += 1

dic = {}
for i in data:
    dic[i] = 1

for i in range(2, 101):
    x = i
    for j in data:

        while x % j == 0:
            x //= j
            dic[j] += 1

count = 1
for i in dic.values():
    count *= i
print(count)

Answer

39001250856960000