质数

HopeAndLizz · 2020-07-06 21:41:41 · 个人记录

质数

定义

质数又称素数。

一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

质数数分布定理

在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的质数大约有 N/lnN 个,即每lnN个数中有一个质数。

也就是说，对于正整数n，定义\pi(n)不大于n的质数个数,则有

\operatorname{\pi(n)}\approx\dfrac{n}{\operatorname{ln}n}

算术基本定理

任何一个大于1的正整数都能唯一分解成有限个质数的乘积，可写作：

N=p_1^{c1}\,p_2^{c2}\,\cdots\,p_n^{cm}\,\,

其中ci都是正整数，pi都是质数且满足p_1<p_2<\cdots<p_m

并且可以证明：p_1..p_m里最多只有一个质数满足p>\sqrt{N}

正约数个数定理

按上述分解质因式后可得

\operatorname{T(A)}=(c_1+1)(c_2+1)\cdots(c_m+1)

其中包括1和A这两个约数

约数和定理

按上述分解质因式后可得

\operatorname{S(A)}=(1+p_1+\cdots+p_1^{c1})(1+p_2+\cdots+p_2^{c2})\cdots(1+p_m+\cdots+p_m^{cm})

判断质数

有一个简单而又暴力的算法，即试除法，即扫描 2-\sqrt{N}之间的所有整数，依次检查它们能否整除N。

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2;i <= sqrt(n);i++)  //i*i<=n
        if(n%i == 0) return false;
    return true;
}

筛法

筛法是一种高效的构造素数表的算法。

先假定所有数字都是质数
一个数的倍数（>=2倍）一定不是质数，标记为合数
最后没有被标记的，就是质数，因为找不到一个数i使得数i的倍数为这个数（2..i-1找不到它的约数）

埃氏筛法

Eratothenes----埃拉托色尼斯筛法

因为小于x^2的x的倍数在扫描更小的数时已经被标记，所以对于每个x把大于等于x^2的x的倍数标记为合数即可。

复杂度\operatorname{O}(n\log{\log}n)非常接近线性

void get_prime1()
{
    memset(v,0,sizeof(v));  //质数标记
    int tot=0;
    long long i,j;
    for(i=2;i<=n;i++)
    {
            if(v[i])  continue;   //优化1
            prime[tot++]=i;
            for(j=i*i;j<=n;j=j+i)   //优化2
                v[j]=1;
    }}

线筛

埃氏筛法过程中，许多数据还是被不同的质数重复筛，可以继续进行优化。比如12=3*4=2*6

优化的方法：给每个数确定一种唯一筛法（给每个数确定一种唯一的产生方式）

线性筛法通过从大到小累积质因子的方式标记每个合数。让每个合数被他的最小质因子筛掉。

欧拉筛code：

int m;//总共质数个数
int v[MAXN];//最小质因子 
int prime[MAXN];//质数合集 
inline void getpri()
{
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)//如果之前都没被标记，就是质数 
        {
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++)//枚举已获得的质数
        {
            int p=prime[j];
            if(p>v[i]||p*i>n) break;
            //p>v[i]是为了只让最小质因子标记合数，如果删掉还是会重复筛 
            v[i*p]=p;
        }
    }
}

区间筛法

题目1：素数密度

题目2：Prime Distance

思路：因为R过大，用筛法直接筛出范围内所有质数撑不住，于是我们把目光放到\sqrt{R}身上。

易得：区间[L,R]的合数必然有质因子\le \sqrt{R}

因此我们处理[2,\sqrt{R}]的质数p，处在区间[L,R]的p的的k倍（k>1）一定是合数，剩下没被标记的就是质数。

区间筛法可以写成：

if(l==1) v[0]=1;//1不是质数！ 
for(int i=1;i<=m&&prime[i]*prime[i]<=r;i++)
    {//prime[i]存的是sqrt(R)的质数 
        long long p=prime[i];
        long long start=max((l+p-1)/p*p,2*p);
        //start是处在区间内能被p整除的第一个数
        // (l+p-1)是用于向下取整，后面会解释 
        for(long long j=start;j<=r;j+=p)
        {
            v[j-l]=1;//j比较大，我们用v[j-l]表示j是否被标记 
        }
    }
    cnt=0;
    for(long long i=l;i<=r;i++)//以防爆int 
    {
        if(v[i-l]==0)
        {
            pri[++cnt]=i;//区间内质数 
        }
    }

这里需要解释一下为什么是max((l+p-1)/p*p,2*p)表示在[L,R]中第一个被p整除的合数

首先我们知道，要标记合数，所以这个数必须是p的k(k>1)倍，所以为了防止自己本身被标记，所以要**判断
我们假设(l+p-1)/p \ge 2,现验证(l+p-1)/p*p为大于L的且能被整除的第一个数

规定：[x]为小于x的最大整数

\boxed{\begin{matrix} \text{设}\left\lfloor\dfrac{l+p-q}{p}\right\rfloor *p \text{一定能取到大于L的且能被整除的第一个数}\\\\\text{1.假设}l=k*p+r,1\le r< p\\\therefore \text{大于L的且能被整除的第一个数为(k+1)*p}\\\text{代入}\\\therefore\left\lfloor\dfrac{l+p-q}{p}\right\rfloor =\left\lfloor\dfrac{p*(k+r+1)-q}{p}\right\rfloor=\left\lfloor k+r+1-\dfrac{q}{p}\right\rfloor\\\because \left\lfloor k+r+1-\dfrac{q}{p}\right\rfloor=k+1\text{恒成立}\\\therefore 1\le r+1-\dfrac{q}{p} <2\\\because -p<-r \le -1 \\\text{同向加法原则}\\\therefore 0<\dfrac{q}{p}<p\\\therefore 0<q<p^2\text{恒成立}\\\because p^2\,\,(p\ge 2)\text{单调递增}\\\therefore \text{代入2得}p^2=4\\\because q\text{为整数}\\\therefore q\text{取}1,2,3\\\\\text{2.假设}l=k*p\\\therefore \text{大于L的且能被整除的第一个数为k*p}\\\text{易得}0<q\le p\\\therefore q\text{取}1,2\\\\\text{综上}q\text{可取}1,2\end{matrix}}

从以上可以推出，不仅是q=1,q=2也是满足条件的，因此题目1的代码如下：

#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=1e6+10;
int prime[4800];
int v1[46341];
int m;//4792
int l,r,cnt;
int v[MAXN];
int pri[MAXN];
int x1,y1,x2,y2;
inline void getpri()
{
    for(int i=2;i<=46340;i++)
    {
        if(v1[i]==0)
        {
            prime[++m]=i;
            v1[i]=i;
        }
        for(int j=1;j<=m;j++)
        {
            int p=prime[j];
            if(p>v1[i]||p*i>46340) break;
            v1[p*i]=p;
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&l,&r);
    getpri();
    memset(v,0,sizeof(v));
    if(l==1) v[0]=1;//1不是质数！ 
    for(int i=1;i<=m&&prime[i]*prime[i]<=r;i++)
    {//prime[i]存的是sqrt(R)的质数 
        long long p=prime[i];
        long long start=max((l+p-1)/p*p,2*p);//减2也能过
        //start是处在区间内能被p整除的第一个数
        // (l+p-1)是用于向下取整，后面会解释 
        for(long long j=start;j<=r;j+=p)
        {
            v[j-l]=1;//j比较大，我们用v[j-l]表示j是否被标记 
        }
    }
    cnt=0;
    for(long long i=l;i<=r;i++)//以防爆int 
    {
        if(v[i-l]==0)
        {
            cnt++;//区间内质数 
        }
    }
    printf("%d",cnt);
}
//要记得注释掉open