分解質因數

分解質因數

每個合數都可以寫成幾個質數相乘的形式，其中每個質數都是這個合數的因數，把一個合數用質因數相乘的形式表示出來，叫做分解質因數。如30=2×3×5 。分解質因數只針對合數。

目錄
1定義 2定理 3編程分解 C#
pascal Java Visual Basic c語言
C++ Common Lisp Python 2.x Python 3.x
Bash Shell 批處理 javascripts

定義

把一個合數分解成若干個質因數的乘積的形式，即求質因數的過程叫做分解質因數。
分解質因數只針對合數。（分解質因數也稱分解素因數）求一個數分解質因數，要從最小的質數除起，一直除到結果為質數為止。分解質因數的算式叫短除法，和除法的性質差不多，還可以用來求多個個數的公因式。

定理

不存在最大質數的證明：（使用反證法）
假設存在最大的質數為N，則所有的質數序列為：
設，
可以證明不能被任何質數整除，得出也是一個質數。
而，與假設矛盾，故可證明不存在最大的質數。
第二種因數分解的方法：
1975年，John M. Pollard提出。該演演算法時間複雜度為。詳見參考資料。

編程分解

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void Main(string[] args)
{
Practice3();
}
private static void Practice3()
{
List a = new List(); //用於存放質因數
Console.WriteLine("請輸入一個整數：");
int n = Convert.ToInt32(Console.ReadLine());
int o = n; //用於存放輸入的整數
for (int x = 2; x <= n; x++)
{
if (n % x == 0)
{
n /= x;
a.Add(x);
x--; //為了防止該整數有多個相同質因數最終只能輸出一個的情況
}
}
Console.WriteLine("{0}={1}", o, string.Join("*", a.ToArray()));
}
另一種實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include 
Integer m,b,c := 0,j := 0;
Integer a[10]; //存放質因數
Integer fjzys(Integer k)
begin
Integer i := 2;
while (k> := i) do //判斷k是否合格
begin
if (k mod i=0) then //判斷k是否整除當前因數
begin
a[j] := i; //存入因數
k/ := i; //餘數
i := 2; //令i重新等於2
j++; //計數值
end
else
begin
i++; //不能整除則當前因數為非質因數
end;
end;
(* C2PAS: Exit *) Result := 0;
end;
(* 用for實現上面的函數
int fjzys(int k)
{
int i=2;
for ( ; i<=k ; i++ ) //當因數i<=k時，實現該循環，每次循環因數i自加1
for ( ; k%i==0 ; j++ ) //當k整除當前因數，實現該循環，每次循環下標j自加1
{
k/=i; //使k=k/i
a[j]=i; //存入因數
}
return 0;
}
解決上面的函數，無法輸出，多個相同的質因數，如90=2*3*3*5，只能輸出一個3.
*)
void main()
begin
printf('請輸入一個整數'#10'k=');
scanf('%d', (* C2PAS: RefOrBit? *)&m);
fjzys(m);
for(b := 0;b<(j-1);b++) 
freopen("F://1.txt", "r", stdin);
freopen("F://2.txt", "w", stdout);
while (scanf("%lld", &in) != EOF)
{
b = 0;
for (i = 2; in != 1; i++)
{
if (in%i == 0)
{
in /= i;
b ? printf("%d", i) : printf("%d", i), b = 1;
i--;
}
printf("\n");
}
}
return 0;
}
實現二
可直接在VC6.0運行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include 
int m, b, c = 0, j = 0;
int a[10]; //存放質因數
int fjzys(int k)
{
int i = 2;
while (k >= i) //判斷k是否合格
{
if (k%i == 0) //判斷k是否整除當前因數
{
a[j] = i; //存入因數
k /= i; //餘數
i = 2; //令i重新等於2
j++; //計數值
}
else
{
i++; //不能整除則當前因數為非質因數
}
}
return 0;
}
 
int main()
{
printf("請輸入一個整數\nk=");
scanf("%d", &m);
fjzys(m);
for (b = 0; b < (j - 1); b++) //*比質因數少一個
{
printf("%d", a[b]);
printf("*");
}
printf("%d\n", a[j - 1]); //輸出最後一個質因數
return 0;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include
using namespace std;
int main()
{
int n,n2;
cout<<"請輸入需要分解的質因數:"
cin>>n;
cout<
n2=n;
if(n<2){
return 0;//n小於2返回自身
}
cout<<"1*"; //輸出 1*
for(int i=2;i*i<=n2;i++)//for循環窮舉質因數
{
while(n2%i==0)//while循環判斷質因數
{
n2=n2/i;//獲得質因數
cout<
if (n2!=1)//判斷質因數
cout<<"*";//輸出乘號
}
}
if(n2!=1){//判斷質因數
cout<
}
return 0;//返回
}
//法2：
#include 
using namespace std;
int main()
{
 int n;
 cin>>n;
 int m=n;
 int flag=0;
 cout<
 for(int i=2;i*i<=n;i++)
 {
if(n%i==0)
{
int cnt=0;
while(n%i==0)
{
n=n/i;
cnt++;
}
if(flag==1) printf("*"); 
if(cnt==1)
{
printf("%d",i);
} 
else
{
printf("%d^%d",i,cnt);
}
flag=1;
}
} 
if(n>1)
 {
if(flag==1)printf("*");
printf("%d",n);
}
 return 0;
}

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

Python 2.x

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/python
# -*- coding:utf-8 -*-
 
num = int(raw_input("請輸入要分解的正整數："))
 
temp = []
while num!=1:
for i in range(2,num+1):
if num%i == 0:
temp.append(i)
num /= i
break
print temp

Python 3.x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#MillerRabin素數判定，結合Pollard_rho遞歸分解，效率極高
 
import random
from collections import Counter
 
def gcd(a, b):
if a == 0:
return b
if a < 0:
return gcd(-a, b)
while b > 0:
c = a % b
a, b = b, c
return a
def mod_mul(a, b, n):
result = 0
while b > 0:
if (b & 1) > 0:
result = (result + a) % n
a = (a + a) % n
b = (b >> 1)
return result
def mod_exp(a, b, n):
result = 1
while b > 0:
if (b & 1) > 0:
result = mod_mul(result, a, n)
a = mod_mul(a, a, n)
b = (b >> 1)
return result
def MillerRabinPrimeCheck(n):
if n in {2, 3, 5, 7, 11}:
return True
elif (n == 1 or n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0):
return False
k, u = 0, n - 1
while not (u & 1) > 0:
k += 1
u = (u >> 1)
random.seed(0)
s = 5
for i in range(s):
x = random.randint(2, n - 1)
if x % n == 0:
continue
x = mod_exp(x, u, n)
pre = x
for j in range(k):
x = mod_mul(x, x, n)
if (x == 1 and pre != 1 and pre != n - 1):
return False
pre = x
if x != 1:
return False
return True
def Pollard_rho(x, c):
(i, k) = (1, 2)
x0 = random.randint(0, x)
y = x0
while 1:
i += 1
x0 = (mod_mul(x0, x0, x) + c) % x
d = gcd(y - x0, x)
if d != 1 and d != x:
return d
if y == x0:
return x
if i == k:
y = x0
k += k
 
def PrimeFactorsListGenerator(n):
result = []
if n <= 1:
return None
if MillerRabinPrimeCheck(n):
return [n]
p = n
while p >= n:
p = Pollard_rho(p, random.randint(1, n - 1))
result.extend(PrimeFactorsListGenerator(p))
result.extend(PrimeFactorsListGenerator(n // p))
return result
 
def PrimeFactorsListCleaner(n):
return Counter(PrimeFactorsListGenerator(n))
PrimeFactorsListCleaner(1254000000)

Bash Shell

1
2
3
#!/usr/bin/bash
read input
factor "$input"

批處理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
@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
echo %mod%
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:~1%
if %num0% EQU %numx% echo %num0%是素數，不能分解！&pause >nul&goto start
echo %num0%=%numx%
pause >nul
goto start

javascripts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function prime(maxValue) {
var minPrime = 2;
var primes = [minPrime];
for (var i = 3; i <= maxValue; i++) {
var isPrime = true;
for (var p = 0; p < primes.length; p++) {
if (i % primes[p] == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes.push(i);
}
} return primes;
}
function decomposition(v) {
var results = [];
var primes = prime(v);
var tmp = v;
for (var i = 0; i < primes.length; i++) {
if (tmp == primes[i]) {
results.push(primes[i]);
break;
}
while (tmp % primes[i] == 0) {
tmp /= primes[i];
results.push(primes[i]);
}
}
if (results.length == 1) {
results = [];
results.push(1);
results.push(v);
}
return results;
}

基本信息

中文名
分解質因數
外文名
Prime factor decomposition
定義
求質因數的過程
別名
分解質因子