数论学习之质数

2024-04-20 18:18

文章标签 学习质数数论

本文主要是介绍数论学习之质数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我们主要介绍两种高效的找质数的方法。
1、埃式筛法
对于一个质数x，我们知道x的倍数肯定不是质数了，如：2是质数，所有2x2，2x3，2x4这些都不是质数了。我们利用一个数组v来进行标记，没被标记的就是质数了。时间复杂度为 $O （ N l o g l o g N ）$
代码：

//埃式筛
void primer(int n){memset(v,0,sizeof(v));for(int i=2;i*i<=n;i++){if(v[i])  continue;for(int j=i+i;j<=n;j+=i){v[j]=i;}}
}

2、线性筛法（用于找每个数的最小的质因数）
线性筛是比埃式筛更加高效得以一种寻找质数的方法。我们知道，如果用埃式筛的话，会有一些重复的被标记的数，所以我们利用线性筛法寻找每个数最小的质因数。其思路就是对于每个数i，当前记录下的素数分别与这个当前的i相乘而且不超过n的数进行标记即可。时间复杂度为 $O （ N ）$
代码：

//线性筛法
const int maxn=1000010;
int v[maxn],prime[maxn];
void primers(int n){memset(v,0,sizeof(v));m=0;for(int i=2;i<=n;i++){if(v[i]==0){  //如果这个数为质数 v[i]=i;prime[++m]=i;}for(int j=1;j<=m;j++) {if(prime[j]>v[i]||prime[j]>n/i)  break; //如果i有比prime[j]更小的质因数，或者超过了n的范围 v[i*prime[j]]=prime[j];}}
}

接下来，我们来介绍一下对一个数n进行质因数分解。
我们接用埃式筛法来进行一下，每找到一个素数的话，我们直接记录下这个素数，然后不断更新n，即缩小n的范围。
代码：

void divide(int n){int m=0;for(int i=2;i*i<=n;i++){if(n%i==0){p[++m]=i;  //记录下这个素数c[m]=0;while(n%i==0){  //不断更新nn/=i;c[m]++;}}}if(n>1)  p[++m]=n,c[m]=1;