分解質因數

分解質因數

任何一個合數都可以寫成幾個質數相乘的形式。其中每個質數都是這個合數的因數,叫做這個合數的分解質因數。分解質因數隻針對合數。
  • 中文名稱
    分解質因數
  • 外文名稱
    Decomposition of the quality factor
  • 釋義
    求質因數的過程叫做分解質因數

​原理方法

舉個簡單例子: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<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個數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<iostream.h>

/*

吳龍武

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."<<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)))))))

相關詞條

其它詞條