素数

高斯素数定理


估计不超过x的素数个数,比真实值略小

$\pi(x) \sim \frac{x}{\ln x}$


素性测试


判断$P$是否为素数

试除法

1
2
3
4
5
6
7
bool isprime(int x){//简单优化:预处理素数表
if(x<2) return false;
int m=sqrt(x+0.5);
for(int i=2;i<=m;i++)
if(x%i==0) return false;
return true;
}

$O(\sqrt{n})$

Wilson theorem

$(P-1)! \equiv -1 \pmod{P}\Rightarrow P$为素数

由于阶乘爆炸增长,无法实际应用

Miller-Rabin测试

基于一定概率的快速判断方法

以下为两个素数的定理(逆定理不成立,但正确率很高)

定理一:费马小定理的逆定理

$(a,P)=1$且$a^{P-1} \equiv 1 \pmod{P}\Rightarrow P$为素数

但是这是不正确的

卡迈克尔数:一个合数$x$,对于所有满足$(a,x)=1$的正整数$a$都有$a^{x-1}$ $\equiv 1$ $\pmod{x}$成立

定理二:二次探测定理

$0 <x < P$,$x^2 \; \% P=1$且$x=1$或$x=P-1$$\Rightarrow P$为素数

也存在问题……

结合两个定理多次选取基底测试,错误率可以忽略不计

$O(k\log )$,$k$为选取的基底个数


唯一分解定理


用质因数分解序列唯一表示一个大数

任何大于$1$的自然数,都可以唯一分解成有限个质数的乘积

因子数与因子和

由乘法原理,因子数$d(x)=\prod\limits_{i=1}^{k}(e_i+1)$

求一个数的所有因子可以使用dfs实现

由等比数列求和公式,因子和$s(x)=\prod\limits_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}$


质因数分解


试除法

1
2
3
4
5
6
7
8
9
10
11
void resolve(int x)//简单优化:预处理素数表
{
int m=sqrt(x+0.5);
for(int i=2;i<=m;i++){
if(!(x%i)){
base[++cnt]=i;
while(!(x%i)) x/=i,++idx[cnt];
}
}
if(x!=1) base[++cnt]=x,idx[cnt]=1;
}

$O(\sqrt{n})$

Pollard Rho算法

非常有趣的算法

采用随机化,通过$Birthday$ $Trick$提高概率,$Floyd$判圈法判断

$O(n^{1/4})$

详解


筛法


埃式筛

1
2
3
4
void Eratosthenes(){
for(int i=2;i*i<=n;i++)
if(!vis[i]) for(int j=i*i;j<=n;j+=i) vis[j]=1;
}

$O(n \log \log n)$

线性筛

筛积性函数

tricks:筛每个数的最小/最大质因子及其幂指数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void euler()
{
for(int i=2;i<=n;i++){//全家桶 d[i]:最小质因子幂 cnt[i]:因子数
if(!vis[i]) p[++p[0]]=i,u[i]=-1,phi[i]=i-1,d[i]=1,cnt[i]=2;
for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]==0){
u[i*p[j]]=0;
phi[i*p[j]]=phi[i]*p[j];
d[i*p[j]]=d[i]+1;
cnt[i*p[j]]=cnt[i]/(d[i]+1)*(d[i]+2);
break;
}
u[i*p[j]]=-u[i];
phi[i*p[j]]=phi[i]*(p[j]-1);
d[i*p[j]]=1;
cnt[i*p[j]]=cnt[i]*2;
}
}
}

$O(n)$

经典课件

杜教筛

解决一类积性函数求前缀和问题

需要表示为两个积性函数卷积的形式

$O(n^{2/3})$

唐教的介绍

州阁筛

要求比较低

$O(\frac{n^{3/4}}{\log n})$

分享到: