1。唯一分解定理

　　总体有三种，这里只说一种，整数的唯一分解定理。

　　整数惟一分解定理亦称算术基本定理，是数论的重要定理之一。该定理断言：任何一个大于1的整数n都可以分解成若干个素因数的连乘积，如果不计各个的顺序，那么这种分解是惟一的，即若n>1，则有

n = p1*p2*…*pm　(1)

　　其中p1≤p2≤…≤pm并满足皆为素数，可以化简为下面的式子：

 

其中，p1<p2<…<pk皆，αi(i=1，2，…，k)皆正整数，(2) 式称为n的标准分解式，又称为质因数分解式、素数幂分解式等，若(2)式成立，则n的任一正因数d都可表成

 

 

 

的形式，其中αi≥βi≥0 (i=1，2，…，k).利用标准分解式(可查素数幂分解表)容易写出任二正整数的最大公因数.即若有 其中αi≥0，βi≥0 (i=1，2，…，k)，则gcd

  

，这里ri=min(αi，βi) (i=1，2，…，k)。

把一个给定的充分大的整数分解成它的标准分解式，不仅具有理论意义，而且具有实际应用价值，但这是一个十分困难的工作，即使借助于电子计算机也要花费惊人的时间，算术基本定理早在(Euclid)的《几何原本》第9卷命题20中已有陈述，1801年，(C.F.Gauss)又重新提出，并给出证明。

 

2。质因数

　　质因数（素因数或质因子）在里是指能整除给定正的。除了1以外，两个没有其他共同质因子的正整数称为。因为1没有质因子，1与任何正整数（包括1本身）都是互质。只有一个质因子的正整数为质数。

 

3。分解质因数

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

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

代码实现：

#include "bits/stdc++.h"using namespace std;typedef long long ll;int main(){    ll n,i;    printf("please input a number:\n");    cin>>n;    cout<
      
       <<"=";    for(i=2;i<=n;i++)    while(n!=i)    {        if(n%i==0)        {            printf("%lld*",i);            n=n/i;        }        else            break;    }    printf("%lld\n",n);    return 0;}
      

上述方法为：Pollard Rho因数分解

1975年，John M. Pollard提出了第二种因数分解的方法，Pollard Rho快速因数分解。该算法时间复杂度为O（n^(1/4)）。

 

将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。

程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成： 

(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。

(2)如果n<>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,

　重复执行第一步。

(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。

 

对于大数的处理，我们可以使用素数表。

a[0]=0;int prim_reduce(int n) //整数素分解{    for(int i = 0; prim[i] * prim[i] <= n; ++i)    {        while(n % prim[i] == 0)        {            n /= prim[i];            a[++a[0]]=pri[i];        }    }    if(n > 1)        a[++a[0]]=pri[i];}

 

4。约数定理个数

对于一个大于1正整数n可以：

 

则n的的个数就是

  

其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。