數先生、數小姐的身份證

素因子分解

我們開首說過，素因子分解 (Prime Factorization) 就好像數字的身份證一樣，因它是惟一的，即除去因子的次序及單位的分解是惟一的，我們稱為惟一分解 (Unique Factorization)。因此沒有兩個不同的數字有一樣的分解式，沒有一個數字有兩條不同的分解式。故其有如我們的身份證一般可辨識身份。事實上，一些極大之數，如過百萬個數位，全數以數位列寫已不可能，以素因子分解式是一有效方法。現在讓我們重溫其計法吧！

1.	若我們欲求 360 的素因子分解式，我們可以短除法求出 360 的所有素因子。雖說測試素因子的大小先後是不會影響結果，但我們仍喜歡以小素數先行。這樣素因子便會自小而大，便利我們抄錄。
2.	我們有 360 =2*2*2*3*3*5。
3.	我們再配合指數運用，便有 360 = 23*32*5，這便是其素因子分解式了。

　

大家亦可在下面的方格輸入數值，本頁的程式會替閣下找出其素因子分解式：

　

 

請輸入一整數 (Integer)：

素因子分解式為：

 

　

我們可以用連乘式表示素因子分解的結：

式中的 p_i 為不同的素因子，而 a_i 則是該素因子的指數，其中 i = 1 至 r。但我們通常喜歡把素因子自小至大列出，以免重覆之誤。

　

「惟一分解定理 (Unique Factorization Theorem)」告訴我們素因子分解是惟一的，這即是稱為算術基本定理 (Fundamental Theorem of Arithmetic) 的數學金科玉律。

其實我們的先進不把 1 視為素數，而稱 1 為單位 (Unit)，正是為了不破壞素因子分解的惟一性。(曾幾何時，數學界把 1 視為素數)

所以惟一可代表數字只有素因子分解式了。除了表示大數有用 (本站內會經常以這方法表示大數) 以外，素因子分解還有其他用武之地，且看下回分解。

　

知不足者

找尋素因子分解的方法很簡單，小學生也曉，但當我們面對一些很大的數時，這方法則有其不足：

首先，我們必須掌握一定範圍的素數，但面對 x > 10²⁰ 以上的數，我們對當中的素數分佈已不盡了解，只知某一些數的素性 (Primality) 而已。

次者，當然我們在程式上可以奇數代替素數作整除性測試 (Divisibility Test) ，但計算步驟會多了很多。即是沒有這樣幹，隨著被分解的數愈大，分解步驟也會愈多。試想一個由 15 位素數乘以 15 位素數的合數，分解它，要由第一個素數開始測試，至第十五數位，需時何其多！

故尋找更快速的計算工具之餘，尋找更高效的分解方法也是必須的。