3.1　素因數分解式

整數分解素因數（又稱分解質因數）是整數分解中最基本的案例。

分解一個整數的素因數并不輕松，甚至是一項艱難繁復的工作。但分解素因數是趣味數學的基礎，眾多趣味數學問題的求解往往離不開整數的素因數分解。

當整數的素因數不太大時整數的素因數分解，并不棘手。例如分解2016，其分解的素因數可寫成以下乘積式與指數式：

2016＝2×2×2×2×2×3×3×7

2016＝2⁵×3²×7

當分解整數的素因數比較大時，素因數分解如何實施？

本節在尋求分解基礎上，編程拓展按指數形式的分解設計，把分解的結果表示為素因數的指數式。

【問題】　對整數n＝201804分解素因數，所分解的素因數按從小到大寫為乘積式。

【思考】　從2，3開始，通過試商逐個找出素因數。

（1）分解思路。

首先求出小于等于]（整數n開平方取整）的所有素數。

注意到[]＝449，小于等于449的素數有2，3，5，7，…，449，共計87個，理論上這87個素數都可能成為201804的素因數。

首先分解出201804的所有2因數，直到變為奇數；然后對余下奇數分解出201804的所有3因數；再對余下奇數依次分解所有5因數、7因數，……，直到分解449因數。

（2）按以上思路分解操作。

①分解201804的2因數：201804/2＝100902，100902/2＝50451，可得2個2因數。

②分解奇數50451的3因數：50451/3＝16817，16817不能被3整除，可得1個3因數。

③對余下數16817通過試商5，7，11，…，61等，沒有這些因數。

④對余下數16817通過試商分解67因數：16817/67＝251，可得1個67因數。

⑤判斷251為素數，即251為素因數。

（3）寫出素因數分解式。

于是得到201804素因數分解式：

201804＝2×2×3×67×251

因[]＝449，原則上要試商小于等于449的所有素數，可見試商分解的工作量是比較大的。本問題由于已得251為素因數，即結束對201804的素因數分解。

【拓展】　對給定的正整數n分解素因數，表示為素因數從小到大順序的指數形式。

如果被分解的整數本身是素數，則注明為素數。

1. 設計要點

為了擴展分解整數的范圍，程序設計采用雙精度型變量。

首先賦值b＝n；，分解操作只對b實施，以保持操作過程中整數n不變。

（1）設置條件循環實施試商。

設置k條件循環（k＝2，3，…，）實施試商，判別k是否為整數n的因數。

注意到整數n的最大因數可能為n/2，用k（2~n/2）試商是可行的，但并不是最省的。事實上，用k（2~）試商可避免許多無效操作，其算法復雜度要低一些。

在k試商循環中，若k不能整除b，說明數k不是b的因數，k增1后繼續試商。若k能整除b，說明數k是b的因數，用j＋＋；統計k因數的個數；同時b除以k的商賦給b（b＝floor（b/k））后繼續用k試商（注意：可能有多個k因數），直至k不能整除b，k增1后繼續試商。

按上述k從小至大試商確定的因數顯然為素因數。

（2）檢測大因數或素數。

如果整數n存在大于（即pow（n，0.5））的因數（至多一個），在試商循環結束后檢測試商后b值。

若b＝1，素因數分解完成。

若b＜n，b即為大于的一個因數，即行輸出。

若b＝n，即整個試商后b的值沒有任何縮減，仍為原待分解數n，說明n是素數，作素數說明標記。

由此可見，對于某些難度較大的素因數分解問題，單憑人工推理計算是難以勝任的，在當今信息時代，必須考慮應用程序設計來解決。

（3）按指數形式輸出。

在素因數指數形式中，首先按素因數從小到大排列；如果存在相同的素因數，要求寫成指數的形式輸出。

在程序設計輸出時，通常把指數上標用^標注，如2³輸出為2^3。

例如分解123456789，按素因數乘積形式為123456789＝3×3×3607×3803，按素因數指數形式為123456789＝3^2×3607×3803。

為此，引入的變量j統計素因子的個數，j＝1時不打印指數；j＞1時需加打指數（^j）。這樣要求程序設計進行必要的判別操作。

2. 素因數分解指數形式程序設計

3. 程序運行示例與說明

     請輸入正整數n:518666803200
     518666803200=2^11×3^3×5^2×7^2×13×19×31

運行程序的整數518666803200是第1章探討的4-完全數，這樣大的數進行素因數分解，應用雙精度型處理是適宜的，若按整型數據處理則并不可行。可見，編程也要依據問題的具體實際情況來定，并沒有千篇一律的固定模式。

順便提到，當整數的素因數比較大時，其分解是艱難的。如果一個中學生想用一個題為難一個數學家，只要選擇兩個比較大的素數a，b，算出a×b＝c，請他在不使用程序設計的前提下分解c的素因數就可以。