1.題目：分解質(zhì)因數(shù)
??將一個(gè)正整數(shù)分解質(zhì)因數(shù)，即分解為由若干個(gè)質(zhì)數(shù)相乘的結(jié)果，例如:輸入90,打印出， 其中2、3、5都是質(zhì)數(shù)。該題目思路比較簡(jiǎn)單，只需要用while for循環(huán)即可解決，適合新手入門python進(jìn)行練習(xí)，本文將由易到難介紹幾種實(shí)現(xiàn)思路，并附上代碼和所需要的知識(shí)點(diǎn)。
2.思路1：首先設(shè)置函數(shù)判斷是否是質(zhì)數(shù)，然后依次進(jìn)行分解
??直接上代碼
#判斷數(shù)據(jù)是否是質(zhì)數(shù)，用于保證大整數(shù)分解時(shí)每一個(gè)因子都是質(zhì)數(shù)
def zhishu(num):
for i in range(2,num):
if num % i == 0:
#print('%d 是個(gè)合數(shù)，可以分解' %num)
return True
#break 樓主之前一個(gè)版本加了break，忽略了函數(shù)return之后其他語(yǔ)句不會(huì)執(zhí)行，相當(dāng)于break了。
else:#和for對(duì)齊，是python獨(dú)有的語(yǔ)法如果for循環(huán)里的語(yǔ)句執(zhí)行結(jié)束后執(zhí)行else語(yǔ)句，如果for循環(huán)里有break則else后的語(yǔ)句不會(huì)執(zhí)行。
#print('%d 是個(gè)質(zhì)數(shù)，請(qǐng)輸入1個(gè)合數(shù)' %num)
return False
def zhiyinshufenjie(num):
nump = num#用于輸出 90 = 2*3*3*5
tmp = []
if not zhishu(num):
print('%num是個(gè)質(zhì)數(shù)，請(qǐng)輸入一個(gè)合數(shù)')#如果是質(zhì)數(shù)則不用執(zhí)行語(yǔ)句
else:
while num:#用于控制循環(huán)次數(shù)直到為0
if not zhishu(num) and num != 1:#排除1，因?yàn)?在分解中沒(méi)有意義
tmp.append(num)
num = 0
else:
for i in range(2, int(num**(1/2))+1):#num**(1/2)為了縮短計(jì)算范圍，在計(jì)算超大數(shù)時(shí)有用
if num % i == 0 & (not zhishu(i)):
tmp.append(i)
num = int(num/i)
#print(i)
break
#print(num)
tmp = sorted(tmp)#排成有序數(shù)組
#設(shè)置打印格式
str1 = ''
for i in range(len(tmp)):
if i== 0:
str1= str1 + str(tmp[i])
else:
str1= str1 + '*' +str(tmp[i])
returnstr = '%d = %s' % (nump,str1)
return returnstr
a=zhiyinshufenjie(888888)
print(a)
這種思路比較簡(jiǎn)單，基本沒(méi)過(guò)大腦，遇到問(wèn)題采用暴力求解的方式解決，存在很多可以優(yōu)化的地方。
3.思路2：優(yōu)化求解法，是在第一種思路下進(jìn)行優(yōu)化
??第二種思路區(qū)別于第一種思路在于，第一個(gè)被整除的數(shù)永遠(yuǎn)是質(zhì)數(shù)，比如1，2，3，5，7，如果是4和6那么也能被2整除。此時(shí)只需要不斷更新被除后的數(shù)，就能計(jì)算出最終的質(zhì)因數(shù)。此處還有幾個(gè)小技巧，如保持除完以后還是整數(shù)，用//，在同一行打印，則設(shè)置print的參數(shù)為end=''。
def fenjiezhiyinshu(num):
n = num
f = []
for j in range(1,num//2+1):
for i in range(2, n):
if n % i == 0:
f.append(i)
n = n//i
break
if len(f) == 0:
print("這是一個(gè)質(zhì)數(shù)，請(qǐng)重新帶入合數(shù)")
else:
f.append(n)
f.sort()
print('%d=%d'% (num,f[0]), end='')
for i in range(1,len(f)):
print('*%d'%f[i] ,end='')
4.思路3：遞歸求解法
??質(zhì)因數(shù)分解時(shí)非常適合做遞歸算法練習(xí)的一個(gè)問(wèn)題，程序的最終出口為不斷輸出可以被輸入值整除的質(zhì)數(shù)，直到最后一個(gè)數(shù)。
import numpy as np
def zhiyinshufenjie(num, tmp):
for i in range(2,int(num**(1/2))+1):
if num % i == 0:
tmp.append(i)
num = num//i
return zhiyinshufenjie(num,tmp)
if len(tmp) == 0:
print('%d是個(gè)質(zhì)數(shù)'%nn)
else:
tmp.append(num)
str1 = ''
for i in range(len(tmp)):
if i== 0:
str1= str1 + str(tmp[i])
else:
str1= str1 + '*' +str(tmp[i])
returnstr = '%d=%s' % (np.cumprod(tmp)[-1],str1)
return returnstr
??由于是遞歸沒(méi)法保存第一個(gè)輸入的num值，因此用了numpy的cumprod函數(shù)對(duì)列表進(jìn)行累乘，得到最初的值。當(dāng)然這個(gè)遞歸還可以寫(xiě)的更簡(jiǎn)單，定義的質(zhì)因數(shù)分解函數(shù)第二個(gè)參數(shù)可以設(shè)置為str，這樣的話第一個(gè)輸入的num值就可以以str形式保存下來(lái)，再不斷迭代得到的輸出格式，這部分留給讀者自己去考慮完成。
