質因數

質因數

質因數(素因數或質因子)在數論里是指能整除給定正整數的質數。除了1以外,兩個沒有其他共同質因子的正整數稱為互質。因為1沒有質因子,1與任何正整數(包括1本身)都是互質。正整數的因數分解可將正整數表示為一連串的質因子相乘,質因子如重複可以指數表示。根據算術基本定理,任何正整數皆有獨一無二的質因子分解式。只有一個質因子的正整數為質數。每個合數都可以寫成幾個質數(也可稱為素數)相乘的形式,這幾個質數就都叫做這個合數的質因數。如果一個質數是某個數的因數,那么就說這個質數是這個數的質因數。而這個因數一定是一個質數(1除外)。

基本信息

定義

質因數質因數
質因數(素因數或質因子)在數論里是指能整除給定正整數的質數。兩個沒有共同質因子的正整數稱為互質。因為1沒有質因子,1與任何正整數(包括1本身)都是互質。正整數的因數分解可將正整數表示為一連串的質因子相乘,質因子如重複可以指數表示。根據算術基本定理,任何正整數皆有獨一無二的質因子分解式。只有一個質因子的正整數為質數

例子

1沒有質因子。

5隻有1個質因子,5本身。(5是質數。)

6的質因子是2和3。(6=2×3)

2、4、8、16等只有1個質因子:2(2是質數,4=2²,8=2³,如此類推。)

10有2個質因子:2和5。(10=2×5)

分解質因數

一個合數用幾個質數相乘的形式表示出來,叫做分解質因數。

分解質因數隻針對合數,把一個合數寫成幾個質數相乘的形式。

分解方法

短除法

質因數質因數
最大公因數的一種方法,也可用來求最低公倍數

求幾個數最大公因數的方法,開始時用觀察比較的方法,即:先把每個數的因數找出來,然後再找出公因數,最後在公因數中找出最大公因數。

例如:求12與18的最大公因數。

12的因數有:1、2、3、4、6、12。

18的因數有:1、2、3、6、9、18。

12與18的公因數有:1、2、3、6。

12與18的最大公因數是6。

這種方法對求兩個以上數的最大公因數,特別是數目較大的,顯然是不方便的。於是又採用了給每個數分別分解質因數的方法。

12=2×2×3

18=2×3×3

12與18都可以分成幾種形式不同的乘積,但分成質因數連乘積就只有以上一種,而且不能再分解了。所分出的質因數無疑都能 整除原數,因此這些質因數也都是原數的約數。從分解的結果看,12與18都有公約數2和3,而它們的乘積2×3=6,就是 12與18的最大公約數。

採用分解質因數的方法,也是採用短除的形式,只不過是分別短除,然後再找公約數最大公約數。如果把這兩個數合在一起短除,則更容易找出公約數和最大公約數。

從短除中不難看出,12與18都有公約數2和3,它們的乘積2×3=6就是12與18的最大公約數。與前邊分別分解質因數相比較,可以發現:不僅結果相同,而且短除法豎式左邊就是這兩個數的公共質因數,而兩個數的最大公約,就是這兩個數的公共質因數的連乘積。

實際套用中,是把需要計算的兩個或多個數放置在一起,進行短除。

在計算多個數的最低公倍數時,對其中任意兩個數存在的約都要算出,其它無此約數的數則原樣落下。最後把所有約數和最終剩下無法約分的數連乘即得到最低公倍數。

只含有1個質因數的數一定是虧數。

Pollard Rho方法

1975年,John M. Pollard提出了第二種因數分解的方法。該算法時間複雜度為O(n^(1/4))。

分解質因數代碼:

將一個正整數分解質因數。例如:輸入90,列印出90=2*3*3*5。

程式分析:對n進行分解質因數,應先找到一個最小的質數k,然後按下述步驟完成:

(1)如果這個質數恰等於n,則說明分解質因數的過程已經結束,列印出即可。

(2)如果n<>k,但n能被k整除,則應列印出k的值,並用n除以k的商,作為新的正整數你n,

重複執行第一步。

(3)如果n不能被k整除,則用k+1作為k的值,重複執行第一步 。

相關搜尋

熱門詞條