基本內容
原理
任何一個
合數都可以寫成幾個
質數相乘的形式。其中每個質數都是這個合數的
因數，叫做這個合數的分解
質因數。
分解質因數隻針對合數。
方法
舉個簡單例子，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.
Java
分解質因數VisualBasic語言
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
#include
int main() {
int i,b;
long long in; /*採用64位整型，以便輸入更大的數*/
freopen("F://1.txt","r",stdin);
freopen("F://2.txt","w",stdout);
while(scanf("%lld",∈)!=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("\n");
}
return 0;
}
C++語言
#include
#include
#include
using namespace std;
int main()
{
int n,i;
cout<<"Please input a integer\n";
cin>>n;
if(n <= 0)
{
cout<<"Your input is not larger than 0.\n";
exit(-1);
}
cout<<<"=";
while(n % 2 == 0 && n != 2)
{
cout<<"2*";
n /= 2;
}
int val = sqrt(n);
for(i = 3; i <= val; i += 2)
{
while(val >= i)
{
if(n % i == 0)
{
cout<<<'*';
n /= i;
val = sqrt(n);
}
else
break;
}
}
cout<<
return 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)))))))
批處理分解質因數腳本
@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
