由网友(可笑的曾经)分享简介：分化量果（Prime factor decomposition）是指每一个合数均可以写成几个量数相乘的情势，此中每一个量数都是那个合数的果数，把1个合数用量果数相乘的情势暗示进去。如三零=二×三×五 。分化量果数只针对于合数。中文名分化量果数释义求量果数的历程[一]外文名Prime factor decomposition,...

分解质因（Prime factor decomposition）是指每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来。

如30=2×3×5 。分解质因数只针对合数。

中文名

分解质因数

释义

求质因数的过程^[1]

外文名

Prime factor decomposition, Prime factorization

又称

分解质因子

定义

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

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

定理

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

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

设M=（N1×N2×N3×N4×……N）+1，

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

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

第二种因数分解的方法：

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

编程分解

另一种实现

c语言

实现一

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

实现二

可直接在VC6.0运行。

CommonLisp

(defun is-prime-number (number)
(let ((num number))
(do ((index 2 （1+ index)))
((>= index num) t)
(if (= 0 (mod num index))
(return-from is-prime-number nil)))))
(defun decomposition-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)))
((>= 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 decomposition-quality-factor nil))))
(setf test-flag t)))))))