唯一分解定理

合数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<w;j++)
    {
        LL tt=0;
        while(n%prime[j]==0)
        {
            n/=prime[j];
            tt++;
        }
        s*=(tt+1);
        if(n==1)
            break;
    }
    if(n>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，是的话就返回0
2：再判断n是不是等于2，是的话就返回1
3：再判断n是不是偶数及(n&1)==0,是的话返回0
4：令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)%n
7: 然后是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的话，肯定不是素数了，返回false
11: 因为Miller-Rabin得到的结果的正确率为 75%，所以要多次循环步骤4~8来提高正确率
12: 循环多次之后还没返回，那么n肯定是素数了，返回true
*/
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll 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<bits/stdc++.h>
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"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

素数判定——埃氏筛法

原理：首先将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<bits/stdc++.h>

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\),该方法依然不是很有效。