每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数写成质因数相乘的形式，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数（即除1和它本身外，还有因数的数）。分解质因数的用途极其广泛，通过分解质因数可以看出这个合数可以被哪些数整除，合数与合数之间公约数和公倍数的关系等。

定义

把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。

分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质差不多，还可以用来求多个个数的公因式。

定理

不存在最大质数的证明：（使用反证法）

假设存在最大的质数为N，则所有的质数序列为：

设，

可以证明不能被任何质数整除，得出也是一个质数。

而，与假设矛盾，故可证明不存在最大的质数。

第二种因数分解的方法：

1975年，John M. Pollard提出。该算法时间复杂度为。详见参考资料。

编程分解

C#

另一种实现

pascal

Java

Visual Basic

c语言

实现一

此代码因为用了long long int，为C99标准，故不可在VC6.0上运行。

实现二

可直接在VC6.0运行。

C++

Common Lisp

(defun IS系列坦克prime-number (number)

(let ((num number))

(do ((index 2 （1+ index)))

((\u003e= index num) t)

(if (= 0 (MOD num index))

(return-from is-prime-number nil)))))

(defun 矩阵分解quality-factor (number)

(let ((num number) (prime-list (make-array 10 :fill-pointer 0 :adjustable t)))

(if (IS系列坦克prime-number num)

(progn

(format t "~a~%" num)

(return-from decomposition-quality-factor nil)))

(do ((index 2 （1+ index)))

((\u003e= index num) nil)

(if (is-prime-number index)

(push index prime-list)))

(dolist (value prime-list)

(let ((test-flag nil))

(do ()

(test-flag nil)

(if (= 0 (MOD num value))

(progn

(format t "~a~%" value)

(setf num (/ num value))

(if (IS系列坦克prime-number num)

(progn

(format t "~a~%" num)

(return-from 矩阵分解quality-factor nil))))

(setf test-flag t)))))))

Python 2.x

Python 3.x

Bash Shell

批处理

javascripts

参考资料