-
質因數
鎖定
質因數例子
- 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)
質因數相關內容
質因數基本信息
質因數
[3]
就是一個數的約數，並且是質數。
比如8=2×2×2，2就是8的質因數；
12=2×2×3，2和3就是12的質因數。
把一個式子以12=2×2×3的形式表示，叫做分解質因數。
把一個合數分解成若干個質因數的乘積的形式，即求質因數的過程叫做分解質因數。
分解質因數只針對合數。（分解質因數也稱分解素因數）求一個數分解質因數，要從最小的質數除起，一直除到結果為質數為止。
分解質因數的有兩種表示方法，除了最常用的“短除分解法”之外，還有一種方法就是“塔形分解法”。
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=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個質因數的數一定是虧數。
