質因數（數學概念）

質因數（數學概念）

質因數 （數學概念） 次瀏覽 | 2022.05.29 13:18:58 更新 來源 ：互聯網 精選百科 本文由作者推薦 質因數數學概念

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

中文名

質因數

英文名

Prime Factors

別稱

素因數或質因子

例子

1沒有質因子

應用學科

數學

例子

1沒有質因子。

5只有1個質因子，5本身。（5是質數）

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

2、4、8、16等只有1個質因子：2。（2是質數，4?=22，8?=?23，如此類推）

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

相關內容基本信息

質因數就是一個數的約數，并且是質數。

比如8=2×2×2，2就是8的質因數；

12=2×2×3，2和3就是12的質因數。

把一個式子以12=2×2×3的形式表示，叫做分解質因數。

把一個合數寫成幾個質數相乘的形式表示，這也是分解質因數?[4]??，如16=2×2×2×2，2就是16的質因數。

把一個合數分解成若干個質因數的乘積的形式，即求質因數的過程叫做分解質因數。

分解質因數只針對合數。（分解質因數也稱分解素因數）求一個數分解質因數，要從最小的質數除起，一直除到結果為質數為止。

分解質因數的方法是先用一個合數的最小質因數去除這個合數，得出的數若是一個質數，就寫成這個合數相乘形式；若是一個合數就繼續按原來的方法，直至最后是一個質數?。

分解質因數的有兩種表示方法，除了最常用的“短除分解法”之外，還有一種方法就是“塔形分解法”。

分解質因數對解決一些自然數和乘積的問題有很大的幫助，同時又為求最大公約數和最小公倍數做了重要的鋪墊。

Pollard?Rho因數分解

1975年，John?M.?Pollard提出了第二種因數分解的方法，Pollard?Rho快速因數分解。該算法時間復雜度為。

分解質因數代碼：

將一個正整數分解質因數。例如：輸入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的值，重復執行第一步。

計算方法

短除法

求最大公因數的一種方法，也可用來求最小公倍數。

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

例1、求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?[4]??。

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

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個質因數的數一定是虧數。

參考資料