用來練手的python 練習題其十四，原鏈接 : python練習實例14

題干 : 將一個正整數分解質因數。例如：輸入90,打印出90=233*5。

拿到題目，我們就可以看出，首先我們需要一個函數來判斷某一正整數是否為質數，然后還需要一個函數來分解質因數。顯然，找到正整數的其中一個質因數是很簡單的，但到這一步還不能幫助我們找到正整數全部的質因數。例如題干中的例子90，我們找到了第一個質因數$2$， $90=2?45$，那么問題就轉化成了45分解質因數，$45=3?15,15=3?5$，直到最后，所有的因數都是質數。

顯而易見，我們可以利用遞歸，將正整數分解質因數的問題轉化為找到正整數的質因數及非質因數，并對非質因數再進行分解質因數直到所有的因數都變為了質因數，遞歸結束，下面為源代碼:

import numpy as np
from math import sqrt# 判斷是否是質數
def prime_number(num):bound_grand = int(sqrt(num))if num == 2 or num == 3:return True#在2-根號num之間如果存在num的因數，則num不是素數for i in range(2,bound_grand+1):if num%i == 0:return Falseelif i == bound_grand:return True
# 使用遞歸分解質因數
def find_prime_factor(num):bound_num = int(sqrt(num))# 如果num已經是質數了，遞歸結束if prime_number(num):print(num)returnfor i in range(2, bound_num+1):# 如果i是num的質因數if num%i == 0 and prime_number(i):print(i)num = int(num/i)# 對非質因數分解質因數find_prime_factor(num)break

代碼包含了兩個函數，一個函數用于判斷某正整數是否為質數。另外一個函數使用遞歸調用分解質因數。

使用結果例如下:

find_prime_factor(10000)