因數分解演算法

① 用短除法分解質因數65

65＝5×13

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

② 分解質因數的方法

1、相乘法

寫成幾個質數相乘的形式（這些不重復的質數即為質因數），實際運算時可採用逐步分解的方式。

如：36=2*2*3*3 運算時可逐步分解寫成36=4*9=2*2*3*3或3*12=3*2*2*3

2、短除法

從最小的質數除起，一直除到結果為質數為止。分解質因數的算式的叫短除法。

(2)因數分解演算法擴展閱讀：

定理

不存在最大質數的證明：（使用反證法）

假設存在最大的質數為N，則所有的質數序列為：N1，N2，N3……N

設M=（N1×N2×N3×N4×……N）+1，

可以證明M不能被任何質數整除，得出M也是一個質數。

而M>N，與假設矛盾，故可證明不存在最大的質數。

最大公約數的求法：

1、用分解質因數的方法，把公有的質因數相乘。

2、用短除法的形式求兩個數的最大公約數。

3、特殊情況：如果兩個數互質，它們的最大公約數是1。

如果兩個數中較小的數是較大的數的約數，那麼較小的數就是這兩個數的最大公約數。

③ 質因數分解演算法

數學中，整數分解（素因數分解）問題是指：給出一個正整數，將其寫成幾個約數的乘積。例如，給出45這個數，它可以分解成32 ×5。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算復雜性理論和量子計算機等領域中有重要意義。
2005年，作為公共研究一部分的有663個二進制數位之長的RSA-200已經被一種一般用途的方法所分解。

如果一個大的，有n個二進制數位長度的數是兩個差不多大小相等的約數的乘積，現在還沒有很好的演算法來以多項式時間復雜度分解它。

這就意味著沒有已知演算法可以在O（nk）（k為常數）的時間內分解它。但是現在的演算法也是比Θ(en)快的。換句話說，現在我們已知最好的演算法比指數數量級時間要快，比多項式數量級時間要慢。已知最好的漸近線運行時間是普通數域篩選法(GNFS)。時間是：

對於平常的計算機，GNFS是我們已知最好的對付n個二進制數位大約數的方法。不過，對於量子計算機， 彼得·秀爾在1994年發現了一種可以用多項式時間來解決這個問題的演算法。如果大的量子計算機建立起來，這將對密碼學有很重要的意義。這個演算法在時間上只需要O(n3)，空間只要O(n)就可以了。 構造出這樣一個演算法只需要2n量子位。2001年，第一個7量子位的量子計算機第一個運行這個演算法，它分解的數是15

如果想獲得最新消息，請你上wikipedia網路，英文版。