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

分解质因数的原理

分解质因数的含义

分解质因数的方法

Pollard Rho快速因数分解

编程分解质因数(pascal语言 Visual Basic语言 c语言 分解质因数算法 批处理分解质因数脚本 C++语言的分解程序 Common Lisp实现分解质因数)

分解质因数的原理

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

分解质因数只针对合数。

分解质因数的含义

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

例如： 12=2x2x3

分解质因数的方法

举个简单例子，12的分解质因数可以有以下几种：12=2x2x3=4x3=1x12=2x6，其中1，2，3，4，6，12都可以说是12的因数，即相乘的几个数等于一个自然数，那么这几个数就是这个自然数的因数。2，3，4中，2和3是质数，就是质因数，4不是质数。那么什么是质数呢？就是不能再拆分为除了1和它本身之外的因数的数，如2，3，5，7，11，13，17，19，23，29等等，质数没有什么特定的规律，不存在最大的质数。

求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法，和除法的性质差不多，还可以用来求多个个数的公因式：

如24

2┖24（是短除法的符号）

2┖12

2┖6

3——3是质数，结束

得出24=2×2×2×3=2^3×3（m^n=m的n次方）

再如105

3┖105

5┖35

----7——7是质数，结束

得出105=3×5×7

证明，不存在最大的质数：

使用反证法：

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

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

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

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

Pollard Rho快速因数分解

1975年，John M. Pollard提出了第二种因数分解的方法。该算法时间复杂度为O（n^(1/4)）。详见参考资料。

编程分解质因数

pascal语言

program dsq;

var

n,i:longint;

begin

readln(n);

write(n,'=1');

i:=2;

while i<=n do begin

while n mod i = 0 do begin

write('*',i);

n:=n div i;

end;

inc(i);

end;

end.

Visual Basic语言

Dim x, a, b, k As String

Private Sub Command1_Click()

a = Val(Text1.Text)

x = 2

If a <= 1 Or a > Int(a) Then

If a = 1 Then

Text2.Text = "它既不是质数，也不是合数"

Else

MsgBox "请您先输入数据", vbOKOnly + vbInformation, "友情提示"

End If

Else

Do While a / 2 = Int(a / 2) And a >= 4

If b = 0 Then

Text2.Text = Text2.Text & "2"

b = 1

Else

Text2.Text = Text2.Text & "*2"

End If

a = a / 2

k = a

Loop

Do While a > 1

For x = 3 To Sqr(a) Step 2

Do While a / x = Int(a / x) And a >= x * x

If b = 0 Then

Text2.Text = Text2.Text & x

b = 1

Else

Text2.Text = Text2.Text & "*" & x

End If

a = a / x

Loop

Next

k = a

a = 1

Loop

If b = 1 Then

Text2.Text = Text2.Text & "*" & k

Else

Text2.Text = "这是一个质数"

End If

End If

End Sub

Private Sub Command2_Click()

Text1.Text = ""

Text2.Text = ""

End Sub

============================================================

c语言 分解质因数算法

#include<stdio.h>

#include<math.h>

int main() {

int i,b;

long long in; /*采用64位整型，以便输入更大的数*/

freopen("F://1.txt","r",stdin);

freopen("F://2.txt","w",stdout);

while(scanf("%lld",&in)!=EOF) { /*在F://1.txt中输入x个数N（N>=2）以换行符或空格符隔开，当没有输入时循环会自动结束*/

b=0; /*用于标记是否是第一个质因数，第一个质因数在输出时前面不需要加空格*/

for(i=2;in!=1;i++)

if(in%i==0) {

in/=i;

b?printf(" %d",i):printf("%d",i),b=1;

i--; /*i--和i++使得i的值不变，即能把N含有的所有的当前质因数除尽，例如：24会一直把2除尽再去除3*/

}

printf("\");

}

return 0;

}

批处理分解质因数脚本

@echo off

color 1e

:start

cls

title 分解质因数程序

set /p num=请输入待分解的数

set num0=%num%

if %num% EQU 1 cls&echo 1既不是素数也不是非素数，不能分解&pause >nul&goto start

if %num% EQU 2 cls&echo 2是素数，不能分解&pause >nul&goto start

if %num% EQU 3 cls&echo 3是素数，不能分解&pause >nul&goto start

set numx=

:loop_1

if %num% EQU 1 goto result

set count=3

set /a mod=num%%2

if %mod% EQU 0 (

set numx=%numx%×2

set /a num=num/2

goto loop_1

)

:loop_2

set /a mod=num%%count

if %mod% EQU 0 (

set numx=%numx%×%count%

set /a num=num/count

)

if %num% EQU 1 goto result

if %count% EQU %num% set numx=%numx%×%count%&goto result

cls

set /a stop=%count%*%count%

if %stop% GTR %num% set numx=%numx%×%num%&goto result

set /a count+=2

echo 正在计算......

echo %num0%=%numx:~2%

set /a wc=stop*100/num

echo 正在计算%num%的因数

echo 已完成计算%wc%%%

if %mod% EQU 0 goto loop_1

goto loop_2

:result

cls

set numx=%numx:~2%

if %num0% EQU %numx% echo %num0%是素数，不能分解！&pause >nul&goto start

echo %num0%=%numx%

pause >nul

goto start

C++语言的分解程序

#include<iostream.h>

/*

吴龙武

20080814

分解质因数

*/

void main()

{

int n,i;

cout<<"Please input a integer\";

cin>> n;

if(n<=0)

{

cout<<"Your input is not larger than 0.\ Now the program will exit."<<endl;

exit(-1);

}

cout<<n<<"=";

for (i=2;i<=n;i++)

{

while(n>=i)

{

if(n%i==0)

{

cout<<i<<'*';

n=n/i;

}

else

break;

}

}

cout<<n;

cout<<endl;

}

Common Lisp实现分解质因数

(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)))))))