質因數分解

如何分析問題、解決問題？

一個質因數分解的小問題。

如果給定一個數，如果是質數，則除了1和它本身，就沒有其他乘積因子了；如果是合數，則一定能變成若幹個質數相乘的形式。是以質因數分解就是把一個數分解成很多個質數因子的過程。

剛碰到這個問題的時候的想法是：給一個數，然後用質數去除它。但是問題又來了，怎麼知道一個數是否為質數呢？或者說如何自動生成一個質數來作除數呢？總不可能先給一個自己寫一個數組然後自己敲一些質數進去，每次要除的時候再一個一個檢查過去吧？而且不可能把所有的質數都敲進去。這顯然不是一個好方法。

前段時間做acm，有道題有部分是關于判斷一個數是否為質數的。

由此聯想，先判斷一個數是否為素數，然後再拿這個數來作除數怎麼樣？這樣至少解決了自動生成質數的問題。

但是，如果一個數可以分解成很多個因子，如420可以分解成 2 2 3 5 7

，如果每次分解都要先一大堆運算來生成質數，然後再來做除法，顯然是一個複雜度很大的算法。是以這又不是一個好方法。

其實我們的思路有時候被問題本身的表達形式給限制住了，是以很多時候無法做到思維發散。

就像這個問題，質因數分解，要用一個個質數去除，首先要有質數。一定要這樣嗎？

質數的定義是什麼？則除了1和它本身，就沒有其他乘積因子了。

那我們可以從另一個角度來找解決方案：

從中可以看到，并不需要特意去找一個質數，而是從2開始除就好了，設被除數（任意給定的數）為num，當num被除得沒有2的因子之後，再将除數+1，即y++，繼續做除法。不用擔心結果中會出現4、6、15、24……這些情況，因為，這些本身就是合數，舉例來說，假設num能被6

= 2*3 整除，說明num可以被2或3整除，而做num =

num/y的前提是y=6，即y>2且y>3，也即num已經被除得沒有2和3的因子了。

是以這個算法是從小到大一步步找出所有質因數，而不是先列出質數然後一個個去除。從某中角度上來說像是跳過了中間多餘的環節。

跳過中間多餘環節，就像《浪潮之巅》中所寫的，戴爾/阿裡巴巴都做到了省去了一大部分中間流通環節，是以使成本大大降低，并直接或間接地從中獲益。

（現在一想，其實一開始學因數分解的時候也是用的這種方法，如果是偶數先用2開始除，然後……

）

寫到這兒，主要不是說找到了一個很好的解決分解質因數的方法，

而是從不同的角度切入問題，試着找到更好的解決方案。