唯一分解定理

合数N仅能以一种方式，写成如下乘积的形式：

\(N=P_1^{e_1}P_2^{e_2}P_3^{e_3}…P_r^{e_r}\)其中\(p_i\)为素数，\(P_1<P_2<…<p_r\)，且\(e_i\)为正整数。

N的因子个数为\((1+e_1)(1+e_2)\cdots(1+e_3).\)

N所有因子的合为\((1+P_1+P_1^2+\cdots+P_1^{e_1})(1+P_2+P_2^2+\cdots+P_2^{e_2})\cdots(1+P_r+P_r^2+\cdots+P_r^{e_r}).\)

模板：

//先造素数表prime[]，w为素数表中的素数个数LL num_of_divisors(LL n){    LL s=1;    if(n==0)        return 0;    for(int j=0;j
    
     1)        s*=2;    return s;}
    

反素数

对于任何正整数X，其约数的个数记做\(g(X)\),例如\(g(1)=1,g(6)=4\)。如果某个正整数X满足：对于任意\(i(0<i<X)\),都有\(g(i)<g(x)\),则称X为反素数。

基于因子个数的公式：按照质因数大小递增顺序搜索每一个质因子，枚举每一个质因子的个数。

性质一：一个反素数的质因子必然是从2开始连续的质数。

性质二：N=\(P_1^{e_1}P_2^{e_2}\cdots P_r^{e_r}\),必然\(e_1\geq e_2\geq \cdots \geq e_r\)。

根据这两点性质对搜索进行剪枝优化。

例题：\(n!\)的素因子分解

若\(n !=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{r}^{e_{r}}\)，则\(n !=\prod_{p \leq n} p^{\alpha(p, n)}\)，其中\(\alpha(p, n)=\sum_{j=1}^{\infty}\left[\frac{n}{p^{j}}\right]\)。

线性筛素数 *模板（时间复杂度\(n\log n\)）

void getpri(){    for( int i = 0; i < N; i++)    {        if( !vis[i])            pri[++num]=i;        for( int j = 1; j <= num && pri[j]*i < N; j++)        {            vis[pri[j]*i] = 1;            if( i%pri[j] == 0)                break; //如果i遇到了自己最小的质因子就直接跳出        }    }}//保证每个数只被它最小的质因子筛掉

素数判定——Miller Rabin算法（超大范围找素数）

一个不保证正确的算法（通常来看错误率可以小到忽略不计）

原理：

费马小定理：若\(n\)是奇素数，\(a\)是任意正整数\((1 \leqslant a \leqslant n-1)\)，则\(a^{(n-1)} \equiv 1 \bmod n\)。

二次探测定理：如果P是一个素数，且\(0<x<p\)，则\(x^{2} \equiv 1 \bmod p\)的解为\(x=1\)或\(x=p-1\)。

步骤：

测试\(n\)是否为素数

①

首先将\(n-1\)分解为\(2^sd\)；

每次测试随机选一个介于\([1, N-1]\)的整数\(a\)；

得到测试序列\(a^d\%n,a^{2d}\%n,\cdots,a^{2^sd}\%n\);

②

首先测试\(a^{2^{s} d} \equiv 1(\bmod n)\)是否成立，若不成立，则\(n\)一定为合数

若\(a^d\equiv 1(\bmod n)\)，或存在某个整数\(0 \leq r \leq s-1\)，使\(a^{2^{r} d} \equiv n-1(\bmod n)\)成立，则称通过Miller测试。

若通过测试，则\(N\)有\(\frac{3}{4}\)的几率为素数。

模板：

/*算法过程1：先判断n是不是小于2，是的话就返回02：再判断n是不是等于2，是的话就返回13：再判断n是不是偶数及(n&1)==0,是的话返回04：令p-1 = 2^t*u,此时p是奇数，u是奇数5：随机取一个a，a∈(1,n) a = rand()%n-1 + 1;6: 因为n-1 = u*2^t，所以a^(n-1)=a^(u*2^t)=(a^u)^(2^t),令 x = (a^u)%n7: 然后是t次循环，每次循环都让y = (x*x)%n，x=y,这样t次循环之后x=a^(u*2^t)=a^(n-1)了8: 因为循环的时候y=(x*x)%n，且x肯定是小于n的，正好可以用二次探测定理9: 如果(x^2)%n==1，也就是y等于1的时候，假如n是素数，那么x==1||x==n-1，如果x!=1&&x!=n-1，那么n肯定不是素数了，返回false。10: 运行到这里的时候x=a^(n-1)，根据费马小定理，x!=1的话，肯定不是素数了，返回false11: 因为Miller-Rabin得到的结果的正确率为 75%，所以要多次循环步骤4~8来提高正确率12: 循环多次之后还没返回，那么n肯定是素数了，返回true*/#include
    
     using namespace std;#define ll unsigned long longll mod_exp(ll a,ll b,ll n){ll res = 0;while(b){if(b&1)res = (res + a)%n;a = (a+a)%n;b>>=1;}return res;}ll mod_pow(ll a,ll b,ll n){ll res = 1;while(b){if(b&1)res = mod_exp(res,a,n);a = mod_exp(a,a,n);b>>=1;}return res;}bool miller_rabin(ll n){if(n==2)return true;if(n<=1||!(n&1))return false;ll i,j,t,u;t = 0;u = n-1;while(u&1==0)// n-1 化成 u*2^t u为奇数；{t++;u>>1;}for(i = 0;i < 10; i++){ll a = rand()%(n-1)+1;ll x = mod_pow(a,u,n);for(j = 0;j < t; j++){ll y = mod_exp(x,x,n);if(y==1&& x!=1 && x!=n-1)return false;x = y;}if(x!=1)return false;}return true;}int main(void){ll i,j,t,n;scanf("%llu",&t);while(t--){scanf("%llu",&n);for(i = 1;i < n;i++){if(miller_rabin(i)&&miller_rabin(n-i)){printf("%llu %llu\n",i,n-i);break;}}}return 0;}
    

素数判定——欧拉筛法

#include
    
     using namespace std;const int maxn = 1e7+10;bool book[maxn];int prime[maxn];int cnt;void Init(int n){    cnt = 0;    memset(book,0,sizeof(book));    book[1] = 1;    for(int i = 2; i <= n; i++)    {        if(book[i]==0)        {            prime[cnt++] = i;        }        for(int j = 0; j < cnt && prime[j]*i <= n; j++)        {            book[i*prime[j]] = 1;            if(i%prime[j]==0)                break;        }    }}int main(void){    int n,m;    cin>>n>>m;    Init(n);    for(int i = 0; i < m; i++)    {        int x;        cin>>x;        if(book[x]==0)            cout<<"Yes"<
    

素数判定——埃氏筛法

原理：首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是\(O(nloglogn)\)。

步骤：

在1~n这n个连续的数里面开始筛出合数，知道剩下全部为素数，大致流程如下：

第一步：能够确定1不是素数，所以将1筛出，剩下从2开始的数列

第二步：找到2为第一个素数，那么遍历这个数列，将2的倍数筛出，形成一个新的数列

第三步：找到下一个素数 x，此时 x = 3，那么再次遍历这个数列，筛出 x 的倍数，剩下的数再次形成一个新的数列

第四步：重复第三步，直到将所有合数筛出

模板：

#include
    
     using namespace std;const int MAXN = 0x3f3f3f;typedef long long ll;bool is_prime[MAXN];ll n;ll prime[MAXN];ll t;void isprime(){    is_prime[0] = is_prime[1] = 1;    for( int i = 2; i < n; i++)    {        if( !is_prime[i])        {            prime[t++] = i;            for( int j = 2*i; j < n; j+=i)                is_prime[j] = 1;        }    }}int main(){    cin >> n;    isprime();    cout << t << endl;    for( int i = 0; i < t; i++)        printf("%lld\n", prime[i]);    cout << endl;    return 0;}
    

pollard-rho——大数分解

原理：设\(n\)为待分解的大整数，用某种方法生成a和b，计算\(P=gcd( a-b, n)\)，直到\(P\)不为1或\(a,b\)出现循环为止，若\(P=n\)，则说明\(n\)是一个素数，否则\(P\)为\(n\)的一个约数。

算法步骤：选取一个小的随机数\(x_1\)，迭代生成。

\(x_{[i]}=x_{[i-1]}+c\)，一般选取\(c=1\)，若序列出现循环则退出，计算\(P=gcd( x_{[i-1]}-x_{[i]}, n)\)，若\(P=1\)则返回上一步继续迭代，否则跳出迭代过程。若\(P=n\)，则\(n\)为素数，否则\(P\)为\(n\)的一个约数，并递归分解\(P\)和\(n/P\)。

可以在\(O(sqrt(P))\)的期望时间内找到\(n\)飞一个小因子\(p\)。但对于因子很少，因子值很大的大整数\(n\),该方法依然不是很有效。