质数

· · 算法·理论

质数的判定

暴力判定

```cpp bool is_prime(ll n){ if(n<2) return 0; ll k=sqrt(n); for(ll i=2;i<=k;i++) if(n%i==0) return 0; return 1; } ``` ### 随机化 $O(k\log n)$。 根据费马小定理，若 $p$ 为质数，则 $a^{p-1}=1\pmod p$，虽然反过来不一定成立，但使用多次随机的 $a$ 可以**大概**判定是否为质数，$k$ 可以自己设定一个大一点的数保证结果精确度。 但如果 $n$ 是一些**伪素数**（不是质数却拥有质数的一些特性的数）或判定一段连续的 $n$，则会有较大的出错概率，~~所以这拼的是rp~~，**谨慎使用**。 需要[快速幂](https://www.luogu.com.cn/blog/chenjunxiu/kuai-su-mi-qu-yu)。 ```cpp bool is_prime(int k,ll n){ if(n<2) return 0; for(int i=1;i<=k;i++) if(qmi(rand(),n-1,n)^1) return 0; return 1; } ``` ### Miller_Rabin 算法 需要[龟速乘](https://www.luogu.com.cn/blog/chenjunxiu/jun-su-sheng)的快速版本及其优化的[快速幂](https://www.luogu.com.cn/blog/chenjunxiu/kuai-su-mi-qu-yu)。 #### 变量 - $\texttt{long long pri[14]}$：可用底数数组，其中 $pri_0$ 为个数。 #### 函数 - $\texttt{bool Miller\_Rabin(ll n)}$：判断 $n$ 是否是质数。 #### 代码 ```cpp //long long pri[14]={7,2,325,9375,28178,450775,9780504,1795265022ll}; long long pri[14]={12,2,3,5,7,11,13,17,19,23,29,31,37}; bool Miller_Rabin(ll n){ if(n<3||n%2==0)return n==2; ll u=n-1,t=0; while(!(u&1))u/=2,t++; for(int i=1;i<=pri[0]&&pri[i]<n;i++){ ll a=pri[i],v=qmi(a,u,n),s; if(v==1)continue; for(s=1;s<=t;s++){ if(v==n-1)break; v=mul(v,v,n); } if(s>t)return 0; } return 1; } ``` ## 质数的筛选 ### Eratosthenes 筛法 $O(N\log\log N)$。 ```cpp bool v[N]; void Eratosthenes(int n){ memset(v,0,sizeof(v)); for(int i=2;i<=n;i++){ if(v[i]) continue; for(int j=i;j<=n/i;j++) v[i*j]=1; } } ``` 若 $v_i=0$ 且 $i\ge2$，则 $i$ 是质数。 ### 线性筛法 $O(N)$。 ```cpp int m; int v[N],prime[N]; void Q_prime(int n){ m=0; memset(v,0,sizeof(v)); for(int i=2;i<=n;i++){ if(!v[i]) prime[++m]=v[i]=i; for(int j=1;j<=m;j++){ if(prime[j]>v[i]||prime[j]>n/i) break; v[i*prime[j]]=prime[j]; } } } ``` $prime_{1\sim m}$ 就是 $n$ 以内的质数。 ## 质因数分解 $O(\sqrt N)$。 ```cpp int m; int factor[1600]; void q_factor(int n){ m=0; for(int i=2;i*i<=n;i++) while(!(n%i)) n/=(factor[++m]=i); if(n>1) factor[++m]=n; } ``` $factor_{1\sim m}$ 就是分解后的结果。 ### Pollard-Rho 算法 可在 $O(n^{\frac{1}{4}})$ 的时间内求出 $n$ 的最大质因子。 需要[Miller-Rabin 算法](https://www.luogu.com.cn/blog/chenjunxiu/zhi-shuo)。 ## 宏定义 - $\texttt{\#define get(x)}$：$1\sim x$ 的随机数。 ## 变量 - $\texttt{long long ans}$：最大质因子。 ## 函数 - $\texttt{Pollard\_Rho()}$：初始化随机种子。 - $\texttt{ll gcd(ll x,ll y)}$：$x,y$ 的最大公约数。 - $\texttt{ll work(ll x,ll y)}$：将 $x$ 分解为两数之积。 - $\texttt{void solve(ll x,int t)}$：计算 $x$ 的最大质因子。 - $\texttt{ll ask(ll x))}$：询问 $x$ 的最大质因子。 ## 代码 ```cpp struct Pollard_Rho{ ll ans; Pollard_Rho(){srand(time(0));} ll gcd(ll x,ll y){ return y?gcd(y,x%y):x; } #define get(x) (1LL*rand()*rand()*rand()*rand()%(x)+1) ll work(ll x,ll y){ int t=0,k=1; ll v0=get(x-1),v,d,s=1; v=v0; while(1){ v=(mul(v,v,x)+y)%x; s=mul(s,abs(v-v0),x); if(!(v^v0)||!s)return x; t++; if(t%127==0)if((d=gcd(s,x))^1)return d; if(t==k){ if((d=gcd(s,x))^1)return d; v0=v;k<<=1; } } } void solve(ll x,int t){ if(!(x^1)||x<=ans)return; if(Miller_Rabin(x)){ if(ans<x)ans=x; return; } ll y=x; do{y=work(x,t--);}while(!(y^x)); while(!(x%y))x/=y; solve(x,t);solve(y,t); } ll ask(ll x){ ans=0;solve(x,302627441);return ans; } }pr; ``` [back](https://www.luogu.com.cn/article/dltjrzaa)