目錄

?

一、題目描述

二、思路

1、短除法

2、平方根法

---

一、題目描述

功能:輸入一個正整數，按照從小到大的順序輸出它的所有質因子（重復的也要列舉）（如180的質因子為2?2?3?3?5?）

最后一個數后面也要有空格

輸入描述:

輸入一個long型整數

輸出描述:

按照從小到大的順序輸出它的所有質數的因子，以空格隔開。最后一個數后面也要有空格。

示例1

輸入

180

輸出

2 2 3 3 5

二、思路

1、短除法

1）將2作為正整數的初始質數因子，

2）若正整數不能整除2，則將初始質數因子+1，重復，直到可以被整數為止，

3）若可以被整除了，將下一輪的正整數更新為上一輪正整數除以質數因子的值

4）這個方法比較容易理解，但是在面試題中容易超時，如71,是一個質數，前面70輪都是白做功夫，要是一個更大的質數則會更費時

num = int(input())
multi_num = 2
while num >= multi_num:if num%multi_num == 0:print(multi_num,end = ' ')num = num/multi_numelse:multi_num += 1

2、平方根法

這里主要是因為涉及到一個知識點，那就是每一個正整數的質數因子都不會超過本身的算術平方根+1，這樣會大大降低計算時間

關鍵代碼：

int(num**0.5+1)

prime_num == 1

遞歸

num = int(input())
def f(num):prime_num = 1 # num為質數的標志for i in range(2,int(num**0.5+1)):if num%i == 0: # num整除iprime_num = 0 # num非質數print(i,end=' ')num = num//i # 更新num，接下來的工作就是找新一輪的num的質數因子f(num) # 遞歸break # 遞歸結束條件# 判斷當前數是否為質數if prime_num == 1: # 若從2到int(num**0.5+1)都無法整除num，那說明num是一個質數，直接輸出print(num,end=' ')
f(num)