引入
众所周知，素数的判断在 long long 级别是不能 \(O(\sqrt{n})\) 硬上的。那怎么办呢？？
参考文献。
ababab，先来最低效的。
以下复杂度均考虑高精。
1.试除法
\(O(\sqrt n)\) 枚举，\(n\le 10^{14}\)。
优化
只枚举质数，无法优化预处理质数时间。
2.Millar-Rabin
long long：\(O(k\times(\log n)^3)\)，检验 \(k\) 次，正确率至少 \(1-4^{-k}\)。
极大值域：若广义 Riemann 猜想(GRH)成立，\(O((\log n)^5)\)。
原理
\(x^2\equiv 1(mod\hspace{0.2cm}p)\) 的解有且仅有 \(\pm1\)。
加强（Fermat小定理）
\(x^{p-1}\equiv 1(mod\hspace{0.2cm}p),x\in[2,p-1]\)
同时满足以上两个的很大可能是质数。
考虑随机 \(x\) 验证，注意到任何合数一定会有底数不通过（至少 \(75\%\)）。（如果仅仅是 Fermat 小定理有 Carmichael 数的存在）。
通过前人的努力，int 范围内仅需取 \(\{2, 7, 61\}\)，long long 范围内仅需取 \(\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}\) 或 \(\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}\)（前 \(12\) 个质数）。
优美的实现
同时实现了以上两种判断（好优雅~~）。要写 mul 函数。
const ll bpr[]={};
inline bool miller_rabin(ll p){
if((~p&1)||p<3) return p==2;
ll k=__builtin_ctzll(p-1),mod=p;
--p;p>>=k;
for(int i=0;i<7;++i){
ll a=ksm(bpr[i]%mod,p,mod);
if(a==1||!a) continue;
int j;
for(j=1;j<=k;++j){
if(a==mod-1) break;
a=mul(a,a,mod);
}
if(j>k) return 0;
}
return 1;
}
3.Lucas序列
咕。
4.n-1法
- 定理1
若存在 \(ord_n(a)=n-1\)，则 \(n\) 为质数。
- 定理2
若 \(n-1=FR\)，已知 \(F\) 的所有质因子 \(q\)，且有:
\[\begin{cases} a^{n-1}\equiv1(mod\hspace{0.3cm}n)\\ \gcd(a^{(n-1)/q}-1,n)=1 \end{cases} \]若 \(F>n^{\frac{1}{4}+\epsilon}\)，则 \(n\) 为质数。
只有已知 \(q\) 才行！
n+1 法
咕。
剩下的不管了。
质因数分解（Pollard-Rho）
基本思想
随机出 \(n\) 的一个非平凡因数（\(\in[2,n-1]\)），递归处理。
优化以下，设计一个能取到所有值的不那么随机的随机函数 \(f(x)=(x^2+c)\%n\)
它的图像是 \(\rho\) 型。
根据生日悖论，这里数量小于 \(minp^{\frac{1}{2}}\) 即 \(n^{\frac{1}{4}}\)。
若 \(x_i\equiv x_j\)，则 \(f(x_i)\equiv f(x_j)\)。
即 \(x_{i+k}\equiv x_{j+k}\)。
只要枚举所有 \(k\) 就好了。
这里很简略，代码更草率。
码1，定点前跳
vector<ll>pr;
inline void pollard_rho(ll n){
if(n==1) return ;
if(miller_rabin(n)) return (void)pr.push_back(n);
ll sq=sqrt(n);
if(sq*sq==n) return (void)pollard_rho(sq),pollard_rho(sq);
ll x0=mr()%(n-1)+1,x1=x0,c=mr()%(n-1)+1,d=1,td;
for(int T=1;d==1||d==n;T<<=1){
if(!T) x0=mr()%(n-1)+1,x1=x0,c=mr()%(n-1)+1,T=1;
d=1;
x1=x0;
for(int i=1;i<=T;++i){
x0=ne(x0,c,n);
if(x0==x1){
T=0;
break;
}
td=mul(d,abs(x1-x0),n);
if(td) d=td;
if(!(i&127)){
d=gcd(n,d);
if(d>1) break;
}
}
d=gcd(n,d);
}
pollard_rho(d),pollard_rho(n/d);
}
码2，快慢指针
vector<ll>pr;
inline void pollard_rho(ll n){
if(n==1) return ;
if(miller_rabin(n)) return (void)pr.push_back(n);
ll sq=sqrt(n);
if(sq*sq==n) return (void)pollard_rho(sq),pollard_rho(sq);
ll x0=mr()%(n-1)+1,x1=x0,c=mr()%(n-1)+1,d=1,td;
for(int T=1;d==1||d==n;T<<=1){
if(!T) x0=mr()%(n-1)+1,x1=x0,c=mr()%(n-1)+1,T=1;
d=1;
x1=x0;
for(int i=1;i<=T;++i){
x0=ne(x0,c,n),x1=ne(ne(x1,c,n),c,n);
if(x0==x1){
T=0;
break;
}
td=mul(d,abs(x1-x0),n);
if(td) d=td;
if(!(i&127)){
d=gcd(n,d);
if(d>1) break;
}
}
d=gcd(n,d);
}
pollard_rho(d),pollard_rho(n/d);
}
细节
-
优化 \(\gcd\)，分块+倍增乘起来搞。
-
特判平方数（仅仅加速）。
-
Miller-Rabin 特判
n<=3||n%2==0。