題目
試題 C: 階乘約數
本題總分：10 分
【問題描述】
定義階乘 n! = 1 × 2 × 3 × · · · × n，
請問 100! （100 的階乘）有多少個約數，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，
本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
解題思路
- 首先知道一個定理：就是一個數的約數個數就是它的不同質因數的個數 + 1 再連乘的結果數，
Code
#階乘約數
n = 100
# 因為數不大，就用最普通的方法統計質數了，
p = [2]
for i in range(3, n + 1):
j = 2
while j < i:
if i % j == 0: break
j += 1
else: p.append(i)
#print(p) # 2 3 5 7 ... 97(求出所有的質數，)
m = {}
for i in p: m[i] = 1 # 每個質數初始為 1，代表不選這個質數的可能，
for i in range(2, n + 1): # 遍歷 [2, 100]
x = i
for j in p: # 遍歷質數，將每個被乘數都質因數分解一下，
# （比如 6 分解成 2*3 ，12 分解成 2*2*3）
if j > x: break
while x % j == 0:
x //= j
# 讓對應的質數個數 + 1
m[j] += 1
s = 1
# 所有質因子的個數相乘，就是約數個數了，
for i in m.values():
s *= i
print(s)
Answer
- 39001250856960000
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257465.html
標籤：python