原理方法
举个简单例子：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等等质数，没有什麽特定的规律、不存在最大的质数。
分解质因数用短除法如右图用短除法可以快速进行分解质因数分解过程用质数还能快速求出最大公因数和最低公倍数。你学会了吗快来试一试吧。
什麽是质因数
质数就是除去他自己和1不能被其他的数整除。 合数与质数恰恰相反。 如果两个数只有公约数1那麽这两个数就是互质数。 把一个合数用质因数相乘的形式表示出来叫做分解质因数。两个数相乘这两个数就是它们的积的因数一个数能够被另一数整除这个数就是另一数的倍数。
分解质因数相关示例
求一个数分解质因数要从最小的质数除起一直除到结果为质数为止。分解质因数的算式的叫短除法和除法的性质差不多还可以用来求多个个数的公因式
如24
2┖24是短除法的符号
2┖12
2┖6
3——3是质数结束
得出24=2×2×2×3=2^3×3m^n=m的n次方
再如105
3┖105
5┖35
----7——7是质数结束
得出105=3×5×7
证明不存在最大的质数
使用反证法
假设存在最大的质数为N则所有的质数序列为N1N2N3……N
设M=N1×N2×N3×N4×……N+1
可以证明M不能被任何质数整除得出M是也是一个质数。
而M>N与假设矛盾故可证明不存在最大的质数。
相关分解
Pollard Rho快速因数分解
1975年John M. Pollard提出了第二种因数分解的方法。该演算法时间复杂度为On^1/4。详见参考资料[1-2]。
编程分解质因数
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
#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",&in)!=EOF) { /*在F://1.txt中输入x个数NN>=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;
}
批处理分解质因数脚本
@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
/*
吴龙武
20080814
分解质因数
*/
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."< exit(-1 } cout< for (i=2;i<=n;i++) { while(n>=i) { if(n%i==0) { cout< n=n/i; } else break; } } cout< cout< } 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)))))))
