標籤:分解質因數

每個合數都可以寫成幾個質數相乘的形式,這幾個質數就都叫做這個合數的質因數。如果一個質數是某個數的因數,那麼就說這個質數是這個數的質因數。而這個因數一定是一個質數。

1基本信息

就是一個數的約數,並且是質數,比如8=2×2×2,2就是8的質因數。12=2×2×3,2和3就是12的質因數。把一個式子以12=2×2×3的形式表示,叫做分解質因數。16=2×2×2×2,2就是16的質因數,把一個合數寫成幾個質數相乘的形式表示,這也是分解質因數。
分解質因數的方法是先用一個合數的最小質因數去除這個合數,得出的數若是一個質數,就寫成這個合數相乘形式;若是一個合數就繼續按原來的方法,直至最後是一個質數 。
分解質因數的有兩種表示方法,除了大家最常用知道的「短除分解法」之外,還有一種方法就是「塔形分解法」(參見上圖)。
分解質因數對解決一些自然數和乘積的問題有很大的幫助,同時又為求最大公約數和最小公倍數做了重要的鋪墊。

2定義

分解質因數
一個合數用幾個質數相乘的形式表示出來,叫做分解質因數。
分解質因數只針對合數,把一個合數寫成幾個質數相乘的形式。

3分解方法

Pollard Rho因數分解
1975年,John M. Pollard提出了第二種因數分解的方法,Pollard Rho快速因數分解。該演算法時間複雜度為O(n^(1/4))。

4程序

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<iostream.h>
"
void main()
{
int n,i;
cout<<"Please input a integer\n";
cin>> n;
if(n<=0)
{
cout<<"Your input is not larger than 0.\n 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;
}
批處理分解質因數腳本
@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
上一篇[鳳凰園]    下一篇 [下壩村]

相關評論

同義詞:暫無同義詞