複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/分解質因數/2253749
複製
複製成功

分解質因數

鎖定
每個合數都可以寫成幾個質數相乘的形式，其中每個質數都是這個合數的因數，把一個合數用質因數相乘的形式表示出來，叫做分解質因數，也叫做分解質因子。如30=2×3×5 。分解質因數只針對合數。
中文名
分解質因數
外文名
Prime factor decomposition, Prime factorization
釋    義
求質因數的過程
又    稱
分解質因子

目錄

  1. 1 定義
  2. 2 定理
  3. 3 編程分解

分解質因數定義

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

分解質因數定理

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

分解質因數編程分解

C#
static void Main(string[] args)
{
    Practice3();
}
private static void Practice3()
{
    List<int> a = new List<int>();        //用於存放質因數
    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()));
}
另一種實現
#include <stdio.h>
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++) //*比質因數少一個
begin
printf('%d',a[b]);
printf('*');
end;
printf('%d'#10'',a[j-1]); //輸出最後一個質因數
end;
pascal
//Pascal實現方法於2018.1.28更改，此前版本親測錯誤
//Pascal實現方法於2018.4.7再次更改，將可處理數字的範圍擴大了
{
注意，此程序在處理過大的數字時速度不佳，在各大OJ上估計都會TLE幾個測試數據
}
Var 
  n : Int64 ;
  i : Longint ;
Begin
  readln( n ) ;
  if n<>1 
    then write( n , '=' )
    else write( n , '=1' );
  i := 2 ;
  while n<>1 do 
    Begin
      if ( n mod i )=0 
        then Begin
               n := n div i ;
               write( i );
               if n<>1
                 then write( '*' );
               i := 2 ;
             End
        else inc( i ) ;
    End;
  writeln;
End.
//By Cubeneo（和之前的Rh。是同一個人）
Java
import java.util.Scanner;

public class H6 {
    public static void main(String[] args) {
        System.out.println("輸入所求正整數:");
        Scanner sc = new Scanner(System.in);
        Long n = sc.nextLong();
        long m=n;
        int flag = 0;
        String[] str = new String[50];
        for (long i = 2; i <= n; i++) {
            if (n % i == 0) {
                str[flag] = Long.toString(i);
                flag++;
                n = n / i;
                i--;
            }
        }
        if (flag < 2)
            System.out.println(m + "為質數");
        else {
            System.out.print(m + "=" + str[0]);
            for (int k = 1; k < flag; k++) {
                System.out.print("*" + str[k]);
            }
            System.out.println("\n"+m+"共有"+flag+"個質因數.");
        }
        sc.close();
    }
}
此方法最多可分解包含50個質數的合數.  @author寒鴉LMC
Visual Basic
Dimx,a,b,kAsString
　
PrivateSubCommand1_Click()
a=Val(Text1.Text)
x=2
Ifa<=1Ora>Int(a)Then
Ifa=1Then
Text2.Text="它既不是質數，也不是合數"
Else
MsgBox"請您先輸入數據",vbOKOnly+vbInformation,"友情提示"
EndIf
Else
DoWhilea/2=Int(a/2）Anda>=4
Ifb=0Then
Text2.Text=Text2.Text&"2"
b=1
Else
Text2.Text=Text2.Text&"*2"
EndIf
a=a/2
k=a
Loop
DoWhilea>1
Forx=3ToSqr(a)Step2
DoWhilea/x=Int(a/x)Anda>=x*x
Ifb=0Then
Text2.Text=Text2.Text&x
b=1
Else
Text2.Text=Text2.Text&"*"&x
EndIf
a=a/x
Loop
Next
k=a
a=1
Loop
Ifb=1Then
Text2.Text=Text2.Text&"*"&kv
Else
Text2.Text="這是一個質數"
EndIf
EndIf
EndSub
PrivateSubCommand2_Click()
Text1.Text=""
Text2.Text=""
EndSub
c語言
實現一
此代碼因為用了long long int，為C99標準，故不可在VC6.0上運行。
#include <stdio.h>
#include <math.h>

int main()
{
    int i, b;
    long long int in;
    /*採用64位整型，以便輸入更大的數*/
    freopen("F://1.txt", "r", stdin);
    freopen("F://2.txt", "w", stdout);
    while (scanf("%lld", &in) != 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;
}
實現二
可直接在VC6.0運行。
#include <stdio.h>
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;
}
/* 用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.
*/

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++
#include <iostream>
using namespace std;
int main()
{
    int n,n2;
    cout<<"請輸入需要分解的質因數:" ;
    cin>>n;
    cout<<n<<"=";//輸出等於號 
    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<<i;//返回質因數 
            if (n2!=1)//判斷質因數 
			cout<<"*";//輸出乘號 
        }
    }
    if(n2!=1){//判斷質因數 
	cout<<n2;//輸出質因數 
	}
    return 0;//返回 
}
//法2：
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int n;
 cin>>n;
 int m=n;
 int flag=0;
 cout<<m<<"=";
 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 21+ 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
#!/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
#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
#!/usr/bin/bash
read input
factor "$input"
批處理
@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
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;
}