Python整數因子分解

《計算機算法設計與分析》課後練習題

整數因子分解問題

問題描述：

大于1 的正整數n 可以分解為：n=X1 *X 2 *…*Xm。

例如，當n= 12 時，共有8 種不同的分解式：

12= 12；

12=6x2；

12=4x3；

12=3x4；

12=3x2x2；

12=2x6；

12=2x3x2；

12=2x2x3。

程式設計任務：

對于給定的正整數n，程式設計計算n 共有多少種不同的分解式。

輸入資料第一行有1 個正整數n (1≤n≤2000000000) 。

将計算出的不同的分解式數。

輸入 輸出

input.txt output.txt

12 8

方法一：

def factorization(n):
    for i in range(2,n):
        if n%i==0:
        #當n%i=0時表示i為n的一個因子
            global count
            count=count+1
            #輸出n的一種分解式，用于驗證
            print("{}*{}={} count={}".format(i,n//i,n,count))
            #繼續分解n的一個因子i
            factorization(i)
#從檔案中讀出資料
file_readpath = 'input.txt'
with open(file_readpath) as file:
    txt = file.read()
n=eval(txt)

#初始化count=1，代表n=n*1的情況
count=1
factorization(n)
#輸出結果用于驗證
print("{}共有{}種不同的分解式".format(n,count))

#将結果存入檔案output.txt
file_writepath = 'output.txt'
file=open(file_writepath,"w")
file.write(str(count))
file.close()
           

方法二：

def factorization(n):
    if n == 1:#當商為1時即為已經算出一次分解累計+1
        global count
        count=count+1
    for i in range(2,n+1):#每個數進行周遊
        if n%i == 0:#餘數為0時 即為可分解的數
            factorization(n//i)#進行分解
    return count   
#從檔案中讀出資料
file_readpath = 'input.txt'
with open(file_readpath) as file:
    txt = file.read()
n=eval(txt)

#初始化count=0
count=0
factorization(n)
#輸出結果用于驗證
print("{}共有{}種不同的分解式".format(n,count))

#将結果存入檔案output.txt
file_writepath = 'output.txt'
file=open(file_writepath,"w")
file.write(str(count))
file.close()