质数学习笔记

定义

质数又称素数，有无限个。指一个大于1的自然数，除了1和它本身外，不能被其他自然数整除的数，换句话说就是该数除了1和它本身以外不再有其他的因数;大于1又不是质数的正整数称为合数。

注意:1.1既不是质数也不是合数.2.2是最小的质数也是唯一一个偶数质数

为何质数是无限多的
假设质数有限
分别为\(p_1,p_2,p_3......p_n\)，这里最大的质数是\(p_n\)
有\(m=p_1p_2p_3...p_n+1\)
则\(m\mod p_1=1,m\mod p_2=1,m\mod p_3=1.......m\mod p_n=1\)，显然m%任一个其中的素数都余1
所以m也是一个质数或者有比\(p_n\)更大的质因数，这与假设\(p_n\)是最大的素数矛盾
所以不存在最大的素数 ,所以素数个数无限

定理

算数基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积

下面是来自百度百科的表述：

算术基本定理可表述为：任何一个大于1的自然数 \(N\),如果\(N\)不为质数，那么\(N\)可以唯一分解成有限个质数的乘积\(N=P_1^{a_1}P_2^{a_2}P_3^{a_3}......P_n^{a_n}\)，这里\(P_1<P_2<P_3......<P_n\)均为质数，其中指数\(a_i\)是正整数。这样的分解称为\(N\)的标准分解式。

自我觉得并不是很正确，因为即使\(N\)是个质数，那他也能分解成自己啊，所以任何一个大于1的正整数都能唯一分解为有限个质数的乘积,可写作：

\[ N=p_1^{c_1}p_2^{c_2}……p_m^{c_m} \]

其中\(c_{i}\)都是正整数,\(p_i\)都是质数且满足\(p_1<p_2<p_3......<p_n\)（你也许会说***和上面的不是一样吗，没错就是一样的，我就想打一遍而已）

质数分布定理

对于正实数\(n\)，定义\(\pi(n)\)为不大于\(n\)的质数个数，则有：

\[\pi(n)\approx\frac{n}{\ln n}\]

质数分布定理中的\(n\)越大，这个公式就越准，同时也可以这样写：

\[\lim\limits_{x\to\infty}\dfrac{\pi(x)}{x/ln(x)}=1\]

由质数定理可以给出第\(n\)个质数\(p(n)\)的渐进估计：\(p(n)≈n\ln n\)

知道就好了qwq

质数的判定

试除法

最简单的是从\(2\)判断到\(N\)直接跑一边，判断\(N%i\)是不是为0，但是这样是\(O(N)\)的算法，跑得太慢了，所以我们要想一个效率更高的方法

\(N\)不必呗\(2\)~\(N\)之间的每一个整数去除，只需被\(2\)~\(\sqrt N\)之间的每一个整数去除就可以了。如果\(N\)不能被\(2\)~\(\sqrt N\)间任一整数整除，N必定是素数。因为如果\(N\)能被\(2\)~\(N-1\)之间任一整数整除，其二个因子必定有一个小于或等于\(\sqrt N\)，另一个大于或等于\(\sqrt N\)(也就是说因子是成对出现的).代码实现如下：

bool isPrime(int n){
    if(n==1)return false;//特判N=1的情况 
    int sq=sqrt(n);
    for(int i=2;i<=sq;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

尊享版判断质数

首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；

证明：令\(x≥1\)，将大于等于\(5\)的自然数表示如下：

··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···

可以看到，不和6的倍数相邻的数为\(6x+2，6x+3，6x+4\)，由于\(2(3x+1)\)，\(3(2x+1)，2(3x+2)\)，所以它们一定不是素数，再除去\(6x\)本身，显然，素数要出现只可能出现在\(6x\)的相邻两侧。因此在\(5\)到\(\sqrt{n}\)中每\(6\)个数只判断\(2\)个，时间复杂度\(O(\sqrt{n}/3)\)

int isPrime(int n) {
    float n_sqrt;
    if(n==2 || n==3) return 1;
    if(n%6!=1 && n%6!=5) return 0;
    n_sqrt=floor(sqrt((float)n));
    for(int i=5; i<=n_sqrt; i+=6) {
        if(n%(i)==0 | n%(i+2)==0) return 0;
    }
    return 1;
}

质数的筛选

埃氏筛

埃氏筛法，全称埃拉托斯特尼筛法（什么乱七八糟的），是一种由埃及数学家埃拉托斯特尼所提出的一种简单检定素数的算法，其基本思想是：质数的倍数一定不是质数

实现：
先假设所有的数都是质数，然后从小到大枚举数\(i\)，若\(i\)没有被标记过，则这个数不能被\([2,N-1]\)之间的任何数整除，也就是说，该数就是质数。然后我们把找到的质数的倍数标记为合数，依次判断即可，时间复杂度\(O(N\log \log N)\)

ps:对1进行特判即可

（具体例子找度娘即可，搜索埃氏筛）

代码实现如下：

#include<bits/stdc++.h>
using namespace std;

int pri[10000],vis[1000001];
int n,m=0;

void prime(int n) { 
    memset(vis,0,sizeof(vis));
    for(int i=2; i<=n; i++) {
        if(vis[i])continue;
        pri[++m]=i;
        for(int j=1; j<=n/i; j++) {
            vis[i*j]=1;
        }
    }
}

int main(){
    scanf("%d",&n);
    prime(n);
    for(int i=1;i<=m;i++){
        cout<<pri[i]<<" ";
    }
    return 0;
}

线性筛法（欧拉筛）

在上面的埃氏筛中，我们发现，总有一些数会被标记多次，所以我们要想一个万全之策，只让一个数被标记一次，达到线性复杂度，即\(O(N)\)。

因此我们想到了线性筛，线性筛的基本思路就是使每个数只被筛一次。因为对于两个数\(a\)（质数），\(b\)（合数），\(a*b\)一定为合数。

我们可以通过最小质因数来判断当前合数是否已经被标记过。我们在生成一个需要标记的合数时，每次只向现有的数上乘上一个质因子，并且让它是这个合数的最小质因子，这相当于让合数的质因子从小到大累积，即让每一个合数只由一种方式产生，这样一来每个合数只会被它的最小质因子筛一次，达到了\(O(N)\)的复杂度

代码实现如下：

int num;
int p[N],vis[N];

void prime(int i) {
    for(int i=2; i<=n; i++) {
        if(!vis[i])p[++num]=i;
        for(int j=1; j<=num; j++) {
            if(i*p[j]>n) break;//越界直接break跳出
            vis[i*p[j]]=1;//标记为合数
            if(i%p[j]==0)break;//一个重要的地方，下面要讲
        }
    }
}

为什么要在\(i\mod p[j]==0\)时break呢？

以\(30\)为例：\(30=2\times 3\times 5\)

假设我们没有break，此时\(i=10\)，在用\(p[2]\)也就是\(3\)的时候去筛它的倍数，我们能够将\(30\)标记为合数\((10\times 3=30)\)，而当\(i=15\)时，我们又用\(p[1]\)也就是\(2\)，再次将\(30\)标记了一次\((15\times2=30)\)，那么这样的话\(30\)被标记了多次，就不符合我们所说的线性筛法了，因为我们所说的是每个数只会被标记\(1\)次，所以在\(i%p[j]==0\)时\(break\)，就能够保证每个数都被筛到了一次

那么为何\(p[j]\)就是\(i\)的最小质因子呢？

假如\(i\)有更小的质因子的话，那在筛到\(p[j]\)之前的时候，就已经被枚举到了（因为我们是从小到大枚举质数，当时就要\(break\)），所以\(p[j]\)就是\(i\)的最小质因子

下面我不要脸的把学长课件里的解释搬上来，肯定能帮助你们进一步理解啦

由于我们的\(p\)是从小到大枚举的，可以说\(p[j]\)是\(i\)的最小质因子
当\(i\)能被\(p[j]\)整除时，\(i\times p[j+1]，i\times p[j+2]…\)这些合数也可以被\(p[j]\)整除，若我们不停止循环，这些合数会被别的质数筛掉，也就是说我们没有用最小质质因子去筛的它，这样一个数会被筛多次，降低了效率。

质因数分解

前面我们说过算数基本定理，即任何一个大于1的正整数都能唯一分解为有限个质数的乘积，写作：
\[ N=p_1^{c_1}p_2^{c_2}……p_m^{c_m} \]
（我和谐地又写了一遍）

这其实就是对于N这个数的质因数分解，并且这种分解是唯一的，直接上代码

#include<bits/stdc++.h>
#define N 10100 

using namespace std; 
int c[N],p[N];
int n;

void divide(int n) {
    int num=0;
    for(int i=2; i*i<n; i++) {
        if(n%i==0) {
            p[++num]=i;
            c[num]=0;
        }
        while(n%i==0)n/=i,c[num]++;
    }
    if(n>1)p[++num]=n,c[num]++;
    for(int i=1; i<num; i++)printf("%d^%d*",p[i],c[i]);
    printf("%d^%d",p[num],c[num]);
}

int main(){
    scanf("%d",&n);
    divide(n);
    return 0;
}

质数的相关定理

唯一分解定理

若整数\(a\geq 2\)，那么\(a\)一定可以表示为若干个素数的乘积（唯一的形式）

威尔逊定理

若\(p\)是素数，则\((p-1)!\equiv-1(\mod p)\)
威尔逊定理的逆定理也成立，即：
若对一整数\(p\)，有\((p-1)!\equiv-1(\mod p)\)，则\(p\)一定是素数
威尔逊定理也可写作：若\(p\)为质数,则\(p\)可整除\((p-1)!+1\).
证明：
对于偶质数\(2\),命题显然成立；
对于奇质数,令\(a∈A=\{2,3,4.p-2\}\),则\(B=\{a,2a,3a,.,(p-1)a\}\)中不会有对于除数\(p\)同余的两个数；事实上 \(αa,βa∈B,αa≡βa(\mod p)\),则\(a|α-β|\)能被\(p\)整除,而\(a|α-β|∈B\),\(B\)中的元素不可能被\(p\)除尽.于是\(B\)中被\(p\)除得的余数形成集合\(\{1,2,3,...,p-1\}\).
假设\(b\)中被\(p\)除余一的数是\(γa\):
一.若\(γ=1\),则\(γa=a\),它被\(p\)除余\(a\),所以\(γ=1\)不成立；
二.若\(γ=p-1\),则\(γa=(p-1)a\),它被\(p\)除余\(a\),所以\(γ=p-1\)不成立；
三.若\(γ=a\),则\(γa=a\ast a\),由于\(a\ast a≡1(\mod p)\),故应有\(a\ast a-1=(a+1)(a-1)≡0(\mod p)\),这只能是\(a=1\)或\(a=p-1\),此与\(a∈A\)矛盾,故不成立；
有一二三知\(γ≠a\)且\(a∈A\).
\(a\)不同时,\(γv\)也相异；若\(a1≠a2\),\(a1\),\(a2∈A\),且\(γa1≡γa2≡1(\mod p)\),因,\(γa1,γa2∈B\),而\(B\)中的元素关于\(\mod p\)不同余,可见\(a1≠a2\),则\(γ1≠γ2\).
即每一个\(a\)均可找到与其配对的\(y\)使其\(ay≡1(\mod p)\)
\(∴ 1×2×3×4.(p-2)≡1(\mod p)\)
\(p-1≡-1(\mod p)\)
\(∴ (p-1)!≡-1(\mod p)\)
从而\(p\)可整除\((p-1)!+1\)

费马小定理

若\(p\)为素数，\(a\)为正整数，且\(a\)与\(p\)互质，则\(a^{p-1}\equiv1(\mod p)\).