什么是分解质因数

每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的质因数。

把一个合数用质因数相乘的形式表示出来，叫做分解质因数。

例如:把48分解质因数.

(以下是解题过程)

解:用短除法分解48,得到质因数2,2,2,2,3

即48=2*2*2*2*3

分解质因数的原理

每个合数都可以写成几个质数相乘的形式.其中每个质数都是这个合数的因数,叫做这个合数的质因数.

分解质因数的含义

一个合数用几个质数相乘的形式表示出来,叫做分解质因数.

例：12=2x2x3

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

定理：

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

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

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

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

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

第二种因数分解的方法：

1975年，John M. Pollard提出。该算法时间复杂度为O()。

---