素数专辑（超详细超完善版本）

短命女 2023-03-04 03:22 255阅读 0赞

# 素数的使用 #

1.  素数以及素数性质
2.  素数筛法
3.  素数判断法
4.  素数常见使用点
5.  总结

### 1.素数以及素数性质 ###

##### 1.1素数概念 #####

素数，也称质数。是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

##### 1.2素数性质 #####

质数具有许多独特的性质：  
（1）质数p的约数只有两个：1和p。  
（2）初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。  
（3）质数的个数是无限的。  
（4）质数的个数公式 是不减函数。  
（5）若n为正整数，在 到 之间至少有一个质数。  
（6）若n为大于或等于2的正整数，在n到 之间至少有一个质数。  
（7）若质数p为不超过n（ ）的最大质数，则 。  
（8）所有大于10的质数中，个位数只有1,3,7,9。

### 2.素数筛法（数论方法） ###

一般题目涉及到的素数很大时，用一般的判素方法一位一位去判断有点耗时耗力，这时候常用数论里面的筛法去筛选大素数。这里我们讲到下面两种筛法：埃斯筛法和欧拉筛法

##### 2.1埃斯筛法（时间复杂度O(n\*logn)） #####

**埃斯筛法，全名埃拉托斯特尼筛法。**  
**u\[ \]是一个筛子，也可以看作是一个标记数组，用于标记这个数是素数还是合数**  
设u\[ \]为筛子，初始时区间中的所有数在筛子u\[\]中。按递增顺序搜索u\[\]中的最小数，  
将其倍数从u\[\]中筛去，最终筛中留下的数即为素数。  
**算法代码如下：**

默认使用c++语言
     int i, j, k;
     for (i=2; i<=n; i++) 
     	u[i]=true; //初始时所有数在筛中
     for (i=2; i<=n; i++) //顺序搜索筛中的最小数
     	if (u[i]) 
     	{ 
    		 for (j=2; j*i<=n; j++) //将i的倍数从筛中筛去
     			 u[j*i]=false;
        }
      for (i=2; i<=n; i++) if (u[i])  //将筛中的所有素数放入su[]中
      { 
        su[++num]=i;
      }
      //上述算法的时间复杂度为O(n * log log n)。算法中合数是作为素数的倍数被筛去的。

##### 2.2欧拉筛法（时间复杂度O(n)） #####

欧拉筛法，是相比于埃斯筛法更加高效的一种算法。如果每个合数仅被它最小的质因数筛去，则算法效率可以大幅提升。由此引 出一种优化的算法——**欧拉筛法（Euler’s Sieve）**

int i, j, num=1;
    memset(u, true, sizeof(u));//c++里面用于初始化数组的一个库函数。在string头文件下面
    for (i=2; i<=n; i++)//顺序分析整数区间的每个数
    {  
    	if (u[i]) su[num++]=i; //将筛中最小数送入素数表
    	for (j=1; j<num; j++)//搜索素数表的每个数
    	 {  
    			if (i*su[j]>n) 
    				break; //若i与当前素数的乘积超出范围，则分析下 一个整数i
    			u[i*su[j]]=false; //将i与当前素数的乘积从筛子中筛去
    			if (i%su[j]==0) 
    				break; //若当前素数为i的最小素因子，则分析下一 个整数i
    	}
    }

**题目中尽量选择欧拉筛法会有更短的罚时！！**

### 3.判素方法（常用法） ###

下面讲一些平常数据中常用的判素方法。很实用！！但是无法处理超出c语言最大整型范围的数据

##### 3.1遍历判素法 #####

这种方法也叫直观判断法，最简单，效率也最低

bool judgeprime(int n)
    { 
    	if(n<2) return false;
    	for(int i=2;i<n;i++)//这种判断条件是时间复杂度最高的
    	{ 
    		if(n%i==0)
    			return false;	
    	}
    	return true;
    }

##### 3.2开方判素法 #####

这种方法也很直观,相比前一种优化了循环次数，减少了时间。这种方法稍微利用了数学知识，一个数n的两个因数必然有一个大于sqrt(n),一个小于sqrt(n)。由此优化

bool judgeprime(int n)
    { 
    	if(n<2)
    		return false;
    	for(int i=2;i<floor(sqrt(n));i++)//这里sqrt是对他开根号，floor向下圆整。不理解的py们可以自行查一下圆整（向上和向下）
    	{ 
    		if(n%i==0)
    			return false;
    	}
    	return true;
    }

##### 3.3余六判素法（复杂度基本最优） #####

这种方法使用最简洁的数学推论得到的结论的代码。这种方式在n取得很大的时候优化很明显  
**`结论：大于等于5的素数总是和6的倍数相邻`**

bool judgeprime(int n)
    { 
    	if(n<2) return false;
    	if(n==2||n==3) return true;
    	if(n%6!=1||n%6!=5) return false;//前三个if是判断5以下的素数 
    	for(int i=5;i<=floor(sqrt(n));i++)
    	{ 
    		if(n%i==0||n%(i+2)==0)
    			return false
    	}
    	return true;
    }

### 4.超大素数的判断（超出 long long int 的范围）------Miller-Rabin算法 ###

Miller-rabin算法是一种随机化算法，设n为待检验的整数；k为选取a的次数。重复k次计算，每次在\[1, n-1\]范围内随机选取一个a，若an −1mod n ≠1 ，则n为合数；若随机选取的k个a都使an-1≡1 (mod n)成立，则返回n为素数或伪素数的信息。**这种算法也是目前已知判断素数最快的方法**  
![MILLER-RABIN算法描述][MILLER-RABIN]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2OTc2MjUy_size_16_color_FFFFFF_t_70]

算法详细代码：

#include<cstdio>
    using namespace std;
    typedef long long LL;
    const int prime[3]={ 2,7,61};
    int n,m,x;
    inline char tc(void)
    { 
        static char fl[100000],*A=fl,*B=fl;
        return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
    }
    inline void read(int &x)
    { 
        x=0; char ch=tc();
        while (ch<'0'||ch>'9') ch=tc();
        while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
    }
    inline int quick_pow(int x,int p,int mod)
    { 
        int tot=1;
        while (p)
        { 
            if (p&1) tot=((LL)tot*x)%mod;
            x=((LL)x*x)%mod; p>>=1;
        }
        return tot;
    }
    inline bool Miller_Rabin(int x)
    { 
        if (!(x^2)) return 1;
        if (x<2||!(x&1)) return 0;
        int t=0,u=x-1;
        while (!(u&1)) ++t,u>>=1;
        for (register int i=0;i<3;++i)
        { 
        	if (!(x^prime[i])) return 1;
            if (!(x%prime[i])) return 0;
            int lst=quick_pow(prime[i],u,x);
            for (register int j=1;j<=t;++j)
            { 
                int now=((LL)lst*lst)%x;
                if (!(now^1)&&lst^1&&lst^(x-1)) return 0; lst=now;
            }
            if (lst^1) return 0;
        }
        return 1;
    }
    int main()
    { 
        //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
        read(n); read(m);
        while (m--)
        { 
            read(x);
            puts(Miller_Rabin(x)?"Yes":"No");
        }
        return 0;
    }

### 5.总结 ###

**素数是一类很有用的特殊数据类，很多数学知识都需要用素数做推导。后面常用到的高斯素数等等之类，建立在素数基础上。**

[MILLER-RABIN]: /images/20230208/c3bc8d12389748dc9783649313dea709.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2OTc2MjUy_size_16_color_FFFFFF_t_70]: /images/20230208/778c43a6ff4a440eb225194ded591720.png