数学知识——质数

数学知识——质数

引用

CSDN

1.

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

质数是数学中的一个重要概念，在算法和编程中有着广泛的应用。本文将从质数的判定、质因数分解到筛质数的方法，全面介绍与质数相关的基础知识和算法实现。

一、判定质数

1. 什么是质数？我们小学都学过，质数n是约数只有1和他自身的整数。

2. 如何判定质数？暴力做法是枚举从小到大枚举每个数看能否整除，时间复杂度是O(n)。还有一个方法，如果a是n的约数，那么n/a也是n的约数，对于一对约数（a，n/a），其中较小的数在区间
   ，所以时间复杂度是
   
   。

3. 试除法代码如下：

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;
}

核心思想：x不是质数的条件为x能找到约数对(约数对中较小的数)或x=1

二、分解质因数

1. 小学中的分解质因数如下图：
   由此推出
   其中n中最多只有一个大于
   的因子，原因是如果有两个大于
   
   的因子，相乘会大于n（反证法）

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

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是质数，枚举
次

核心思想：模拟小学分解质因数的过程

三、筛质数

埃式筛法

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

代码如下：

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)

欧拉算法

核心思想：

代码如下：

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)

总结

若n在10的6次方的话,欧拉筛和埃氏筛的时间效率差不多,若n在10的7次方的话,欧拉筛会比埃氏筛快了大概一倍.而且埃氏筛法会重复标记一个合数，而欧拉筛法避免将一个合数标记多次。