分解质因数

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数写成质因数相乘的形式，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数（即除1和它本身外，还有因数的数）。^[1]分解质因数的用途极其广泛，通过分解质因数可以看出这个合数可以被哪些数整除，合数与合数之间公因数和公倍数的关系等。^[2]

把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。

分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似，还可以用来求多个数的公因式。

不存在最大质数的证明：（使用反证法）

假设存在最大的质数为N，则所有的质数序列为：

设，

可以证明不能被任何质数整除，得出也是一个质数。

而，与假设矛盾，故可证明不存在最大的质数。

第二种因数分解的方法：

1975年，John M. Pollard提出。该算法时间复杂度为。详见参考资料。

123456789101112131415161718192021static 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()));}

另一种实现

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <stdio.h>Integer m,b,c := 0,j := 0;Integer a; //存放质因数Integer fjzys(Integer k)beginInteger i := 2;while (k> := i) do //判断k是否合格beginif (k mod i=0) then //判断k是否整除当前因数begina[j] := i; //存入因数k/ := i; //余数i := 2; //令i重新等于2j++; //计数值endelsebegini++; //不能整除则当前因数为非质因数end;end;(* C2PAS: Exit *) Result := 0;end;(* 用for实现上面的函数int fjzys(int k){int i=2;for ( ; i<=k ; i++ ) //当因数i<=k时，实现该循环，每次循环因数i自加1for ( ; k%i==0 ; j++ ) //当k整除当前因数，实现该循环，每次循环下标j自加1{k/=i; //使k=k/ia[j]=i; //存入因数}return 0;}解决上面的函数，无法输出，多个相同的质因数，如90=2*3*3*5，只能输出一个3.*)void main()beginprintf('请输入一个整数'#10'k=');scanf('%d', (* C2PAS: RefOrBit? *)&m);fjzys(m);for(b := 0;b<(j-1);b++) //*比质因数少一个beginprintf('%d',a[b]);printf('*');end;printf('%d'#10'',a[j-1]); //输出最后一个质因数end;

1234567891011121314151617181920212223242526272829//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。是同一个人）

12345678910111213141516171819202122232425262728293031import 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;        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);            for (int k = 1; k < flag; k++) {                System.out.print("*" + str[k]);            }            System.out.println("\n"+m+"共有"+flag+"个质因数.");        }        sc.close();    }}此方法最多可分解包含50个质数的合数.  @author寒鸦LMC

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748Dimx,a,b,kAsString　PrivateSubCommand1_Click()a=Val(Text1.Text)x=2Ifa<=1Ora>Int(a)ThenIfa=1ThenText2.Text="它既不是质数，也不是合数"ElseMsgBox"请您先输入数据",vbOKOnly+vbInformation,"友情提示"EndIfElseDoWhilea/2=Int(a/2）Anda>=4Ifb=0ThenText2.Text=Text2.Text&"2"b=1ElseText2.Text=Text2.Text&"*2"EndIfa=a/2k=aLoopDoWhilea>1Forx=3ToSqr(a)Step2DoWhilea/x=Int(a/x)Anda>=x*xIfb=0ThenText2.Text=Text2.Text&xb=1ElseText2.Text=Text2.Text&"*"&xEndIfa=a/xLoopNextk=aa=1LoopIfb=1ThenText2.Text=Text2.Text&"*"&kvElseText2.Text="这是一个质数"EndIfEndIfEndSubPrivateSubCommand2_Click()Text1.Text=""Text2.Text=""EndSub

实现一

此代码因为用了long long int，为C99标准，故不可在VC6.0上运行。

12345678910111213141516171819202122232425262728#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运行。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <stdio.h>int m, b, c = 0, j = 0;int a;    //存放质因数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;}

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#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;}

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

12345678910111213#!/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            breakprint temp

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#MillerRabin素数判定，结合Pollard_rho递归分解，效率极高 import randomfrom 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)

123#!/usr/bin/bashread inputfactor "$input"

123456789101112131415161718192021222324252627282930313233343536373839404142@echo offcolor 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

12345678910111213141516171819202122232425262728293031323334353637function 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;}