质数相关知识

本篇随笔讲解信息学奥林匹克竞赛相关数学知识中质数的相关内容，大体包括质数的筛选和判定方法。需要读者具有不低于高中一年级的数学基础知识素养，本篇随笔将不再对数学基本知识、概念及符号等进行讲解。请有需要的同学自行补习。

上课！！

1、质数的定义及基本概念

定义：若一个正整数无法被除了1和它自身之外的任何数整除，则称该数为质数（或素数）。否则称该数为合数。

我们需要明确，整个自然数集合中，质数的分布比较稀疏，对于一个足够大的整数\(N\)，不超过它的质数大约有\(\frac{N}{ln N}\)个，换句话说，就是每\(ln N\)个数中大约有1个质数。

2、质数的判定（试除法）

我们需要明确，计算机最优秀的地方在于机械地重复同一件事，针对质数的判定，正好是它的“强项”，我们只需要按照定义入手，枚举从2到n的所有数，如果能整除，就返回false，试到最后还不能的话就返回true。

模板：

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

但是这种方法会浪费大量的时间，假如程序需要多次调用这个函数判质数，就会大大增加算法的时间复杂度。所以我们常用的模板是一种优化版本（想不到吧）

我们这样来想，如果这个数\(N\)能够被一个数\(a\)整除（这个数当然会小于它），那一定还会有另外一个数\(b\)能整除它，而且\(b\cdot a\)一定等于\(N\)。
所以，我们只需要枚举从2到\(\sqrt{N}\)即可。
模板：

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

3、质数的筛选

质数的筛选就是给定数\(N\)，要求找出从1到\(N\)的所有质数。质数的筛选是信竞中很重要的研究课题，也是一些基础数学题的重要解题模型。

(1)Eratosthenes筛法

Eratosthenes筛法即埃斯托拉特尼筛法，简称埃氏筛法。它基于这样的思路：
任意整数的倍数都不是质数
基于这样的想法，我们就从2开始从小到大枚举每个数\(x\)，并把它小于\(N\)的倍数全部打上标记，当我们扫描到一个数的时候，如果它还未被标记，它就是个质数。
这种筛法极好理解，但是效率较低，我们可以拿纸笔模拟，然后就能够发现，有一些数是多个质数的倍数，这样的话它就会被反复筛好几遍（比如说6），这样虽然对正确答案不会造成影响，但却影响程序运行的效率。所以我们对埃氏筛法进行优化：
对于每个数\(x\)，我们从\({x^2}\)开始标记，把\({x^2}\),\((x+1)\cdot x\),\(\cdots\),\(\frac{N}{x}\cdot x\)打标记即可。

优化后模板：

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

(2)Euler筛法

Euler筛法即欧拉筛法，也叫快筛，线性筛法。是信竞中最常用的质数筛法，以伟大的数学家欧拉的名字命名，建议大家熟练掌握。
上述的埃氏筛法即便在优化后也会重复标记，虽然已经少了很多重复，但还是不够快速。比如，12既会被2标记也会被3标记，因为\(12=6\times 2=4\times 3\).为什么会出现这种情况呢？因为我们在按照埃氏筛法筛选的时候，并没有找出确定12的唯一方式，导致12的重复遍历不可避免。
按照这个基础，出现了快筛算法，它的基本思想是这样：我们在生成一个需要被标记的合数的时候，每次只向现有的数中乘上这个合数的最小质因子，这样一来，合数的质因子便被从小到大地累计起来，那刚才的12来说，它就被唯一分解成\(3\times 2\times 2\)。
这个算法的时间复杂度是\(O(N)\)的。

欧氏筛法模板：

void euler(int x)
{
    cnt=0;
    for(int i=2;i<=x;i++)
    {
        if(!v[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=n;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

4、质因数分解

整数的唯一分解定理

这个定理hin重要!!!

整数的唯一分解定理：任何一个大于1的整数都可表示为若干个质数的乘积，表示如下：

即：

所以我们通过如上定理分析出质因数分解在计算机上的实现：
先从2到\(\sqrt{N}\)扫描所有整数\(x\)，如果\(x\)能整除\(N\)，那么就在因子表上加上它，并用\(N\)一直除\(x\)，每次除就在指数表c数组中++，一直到除不尽为止。

代码实现：

void divide(int n)
{
    cnt=0;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            prime[++cnt]=i;
            c[cnt]=0;
        }
        while(n%i==0)
            n/=i,c[cnt]++;
    }
    if(n>1)
        prime[++cnt]=n,c[cnt]=1;
}