数学知识——质数详解

创作时间:

作者:

@小白创作中心

数学知识——质数详解

引用

CSDN

https://blog.csdn.net/lianone_/article/details/145221060

本文详细介绍了质数相关的基础知识和算法实现，包括质数的判定方法、质因数分解以及两种经典的筛质数算法（埃拉托斯特尼筛法和欧拉筛法）。对于编程和算法学习者来说，这些内容具有很高的参考价值。

一、判定质数

什么是质数？我们小学都学过，质数n是约数只有1和他自身的整数。
如何判定质数？暴力做法是枚举从小到大枚举每个数看能否整除，时间复杂度是O(n)。还有一个方法，如果a是n的约数，那么n/a也是n的约数，对于一对约数（a，n/a），其中较小的数在区间，所以时间复杂度是。
试除法代码如下：

bool is_prime(int x)
{
  if(x==1)return 0;
  for(int i=2;i*i<=x;i++)//注意：如果i*i爆int，则i*i改为i<=x/i或i<=sqrt(x)
 {
    if(x%i==0)return 0;
 }
  return 1;
}

core idea:x不是质数的条件为x能找到约数对(约数对中较小的数)或x=1

二、分解质因数

小学中的分解质因数如下图：

其中n中最多只有一个大于的因子，原因是如果有两个大于的因子，相乘会大于n（反证法）

根据分解质因数的过程，模拟如下代码：

int n;
int a[10001];//a[i]为质因子i的个数，用于统计每个质因子出现的个数
void decompose(int x)//分解x的质因数
{
   for(int i=2;i*i<=x;i++)
  {
     while(x%i==0)a[i]++,x/=i;
  }
    if(x>1)a[x]++;//x>1，说明这就是那个大于根下x的质因子
}

时间复杂度为最好情况，循环logn次跑完最坏情况n是质数，枚举次

core idea：模拟小学分解质因数的过程

三、筛质数

埃式筛法

core idea：从小到大（在某个范围里）枚举每个数，如果是质数，则存储起来且标记它的合数们

代码如下：

typedef long long LL;
const int N=100000010;
int vis[N];//vis[i]为1/0，用于标记是否质数
int prim[N];//prim[i]为第i个质数，用于存储质数的数组
int cnt;//cnt为质数个数
void eratosthenes(int n)
{
   for(LL i=2;i<=n;i++)//在[2,n]范围内筛质数
 {
     if(!vis[i])
   {
       prim[++cnt]=i;
       for(LL j=i*i;j<=n;j+=i)//对i的合数们进行标记
          {vis[j]=1;}
    }
  }
}

i的合数们是什么呢？比如2在 [2,20]合数为{4，6，8，10,12,14,16,18,20} 3在[2,20]的合数为{9，12，15，18}，对这些合数进行标记是为了避免他们被当作质数存储进数组。

时间复杂度为O(nloglogn)

欧拉算法

core idea：

代码如下：

const int N = 10000010;
int vis[N]; // vis[i]为1/0，用于标记是否质数
int prim[N]; // prim[i]为第i个质数，用于存储质数的数组
int cnt; // 质数个数
void get_prim(int n){ 
    for(int i=2; i<=n; i++){
        if(!vis[i]) prim[++cnt] = i;
        for(int j=1; 1LL*i*prim[j]<=n; j++){
            vis[i*prim[j]] = 1;
            if(i % prim[j] == 0) break;//prim[j]一定是i的最小质因子。因为prim[j]是从小到大遍历的 一旦出现i%prim[j]=0 prim[j]一定是i的最小质因子 因此prim[j]也一定是i*prim[j]的最小质因子。如果i%prim[j]!=0 prim[j]一定是小于i的所有质因子 因此prim[j]也一定是i*prim[j]的最小质因子。
        }
    }
}

举例说明：

时间复杂度为O(N)