唯一分解定理
合数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_1geq e_2geq 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}} ight])。
线性筛素数 *模板（时间复杂度(nlog 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 mod n)。
二次探测定理：如果P是一个素数，且(0<x<p)，则(x^{2} equiv 1 mod 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(mod n))是否成立，若不成立，则(n)一定为合数
若(a^dequiv 1(mod n))，或存在某个整数(0 leq r leq s-1)，使(a^{2^{r} d} equiv n-1(mod 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
",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
", 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),该方法依然不是很有效。