3.1 素因数分解式
整数分解素因数（又称分解质因数）是整数分解中最基本的案例。
分解一个整数的素因数并不轻松，甚至是一项艰难繁复的工作。但分解素因数是趣味数学的基础，众多趣味数学问题的求解往往离不开整数的素因数分解。
当整数的素因数不太大时整数的素因数分解，并不棘手。例如分解2016，其分解的素因数可写成以下乘积式与指数式：
2016＝2×2×2×2×2×3×3×7
2016＝25×32×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）按指数形式输出。
在素因数指数形式中，首先按素因数从小到大排列；如果存在相同的素因数，要求写成指数的形式输出。
在程序设计输出时，通常把指数上标用^标注，如23输出为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的素因数就可以。