如何將一個數(shù)分解質(zhì)因數(shù)？

如果仔細(xì)來想一下，這個問題其并不是很難。

分析過程：比如，4=2*2，我們可以首先定義一個數(shù)字，然后將這個數(shù)字除以比它本身小的數(shù)字，如果可以整除（也即余數(shù)為0）的時(shí)候，可將此數(shù)保留下來，接著，再將保留下的這個數(shù)再次進(jìn)行分解，直到除了其本身和1以外，不能再被其他比它小的數(shù)整除，即可結(jié)束打印并結(jié)束運(yùn)行。

于是，我們想到了可以使用遞歸函數(shù)實(shí)現(xiàn)這項(xiàng)功能。

代碼如下圖所示。

import time? # 引入時(shí)間，以便能夠測試一下程序運(yùn)行時(shí)間

start = time.time()? # 程序開始運(yùn)行的時(shí)間

number =int(input("請輸入一個整數(shù): "))? # 輸入一個整數(shù)

while number !=1:? ?# 條件判斷，整數(shù)不等于1時(shí)

? ? for iin range(1, number +1):? ?# 輸入的整數(shù)的范圍，在此區(qū)間，且其分解的質(zhì)數(shù)亦在此區(qū)間

? ? ? ? if (number % i) ==0 and i !=1:? ?# 如果此數(shù)遍歷除以比此數(shù)小的數(shù)，余數(shù)為零，且i不等于1 以遞歸函數(shù)實(shí)現(xiàn)此功能

? ? ? ? ? ? number =int(number / i)? ? # 就將次數(shù)除以i并且取整，重新賦值給number

? ? ? ? ? ? if number ==1:? ?# 如果number等于1

? ? ? ? ? ? ? ? print (" %d" %i)? # 打印出i

? ? ? ? ? ? else:? ? # 否則

? ? ? ? ? ? ? ? print (" %d *"%i, end='')? ?# 打印出所有符合條件的質(zhì)因數(shù)i，end=''是為了防止打印的質(zhì)數(shù)換行。

? ? ? ? ? ? break

end = time.time()# 程序結(jié)束時(shí)間

print('程序運(yùn)行時(shí)間為%f'%(end-start))# 打印出程序運(yùn)行時(shí)間差

2020年2月19日

北京市通州區(qū)北運(yùn)河西京貿(mào)中心