数论 --- 朴素筛法、埃氏筛法、线性筛法

数论

组合计数

高斯消元

简单博弈论

质数的定义、质数的判定

质数的定义与判定、分解质因数

第十二届蓝桥杯省赛第二场C++B组真题_小雪菜本菜的博客-CSDN博客

筛质数

先把所有的数写到素数表里面，从前往后看，把每一个数的所有倍数全部筛掉，筛选之后，所有剩下的数就是质数

对于任何一个数 P 而言，它如果没有被删掉的话，就意味着从 2 ~ P - 1 中的任何一个数都没有把 P 筛掉，说明 P 不是 2 ~ P - 1 中任何一个数的倍数，说明 2 ~ P - 1 当中不存在任何一个 P 的约数，所以 P 就是一个质数

 

时间复杂度分析：

当 i 等于 2 的时候循环了 n / 2 次，当 i 等于 3 的时候，循环了 n / 3 次

调和级数

C 是欧拉常数，约为 0.57721566490153286060651209

推导得到朴素筛法的时间复杂度为 O( nlogn )

#include 
#include 
using namespace std;

const int N = 1000010;

int primes[N],cnt;
bool st[N];

void get_primes(int n) 
{
	//从 2 到 n 枚举
    for(int i = 2;i <= n;i++ )
    {
        //如果当前数没有被筛过的话 说明它是一个质数
        if(!st[i]) 
        {
            primes[cnt ++ ] = i;
        }
        //把每一个数的倍数全部筛掉
        for(int j = i + i;j <= n;j += i) st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;    

    return 0;
}

埃氏筛法

我们可以对朴素筛法进行一个优化，可以发现，并不是需要把每一个数的倍数全部删掉，只需要把所有质数的倍数删掉就可以了

按照之前的筛法做筛选，如果留下 P，就说明 P 是一个质数，我们可以发现，其实并不需要把 2 ~ P - 1 全部枚举一遍，只需要把 2 ~ P -1 中的质数判断一遍就可以了

只要保证 2 ~ P - 1 中的所有质数的倍数不是 P( P 是一个质数 )的约数，P 就是一个质因数，在筛选的时候，只需要把质数的所有倍数筛掉就可以了，当一个数不是质数的时候，就不需要筛掉它所有的倍数

时间复杂度分析：现在只需要计算 1 ~ 1 / n 所有质数的调和级数，质数定理：1 ~ n 中有 n / logn 个质数

本来要算 n 个数，现在只需要计算 n / logn 个数，时间复杂度为 O( nloglogn ) 和 O(n) 基本上是一个级别的

从最小的质数 2 开始,，我们知道合数一定是质数的倍数，故我们将筛选到的第一个质数时，我们将它的倍数依次标记为合数，当然不用全部标，只用标记到给出的范围即可。由于是从最小质数开始，故找到的下一个未被标记的数一定也是质数，因为未被标记说明不含2 ~ i - 1 的任何因数，跟上面原理一样。 故将找到的这个新的质数的倍数标记为合数。

首先 1 不是质数也不是合数不考虑

接下来考虑 2，2 是最小的质数，把 2 所有的倍数( 也就是除了 2 以外所有的偶数 )全部筛掉

接下来考虑 3，3 没有被筛掉，说明 3 是质数，把 3 所有的倍数都筛掉，3 的 2 倍其实是不用筛的，因为 2 倍在之前已经被 2 筛过了，可以从 9 开始筛(或者从 6 开始筛，没有什么影响)

筛选 9 之后，下一个要筛选 12，12 在 2 的时候已经被筛过一次，在 3 的时候又被筛选一次，出现重复筛选的问题

接下来看 4，4 是合数，4 的倍数就是 2 的倍数，在 2 的时候已经被筛掉了

接下来看 5，5 没有被筛掉，是质数，开始筛 5 的倍数，5 × 2，5 × 3，5 × 4 被之前的 2、3、4 筛掉，可以从 5 × 5 的位置开始筛，以此类推

11 × 11 = 121 > 100，越界，到达 11 的位置就不用筛了，如果界限是 n，筛选到 √ n 就可以停止

#include 
#include 
using namespace std;

const int N = 1000010;

// primes[]存储所有素数
int primes[N],cnt;
// st[x]存储x是否被筛掉
bool st[N];

void get_primes(int n) 
{
	//从 2 到 n 枚举
    for(int i = 2;i <= n;i++ )
    {
        //如果当前数被筛过的话就跳过
        if (st[i]) continue;
        primes[cnt++] = i;
        //把循环放到判断条件里面 把每一个质数的倍数全部筛掉
        for(int j = i + i;j <= n;j += i) st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;    

    return 0;
}

埃氏筛法比朴素筛法快了 3 倍左右

线性筛法

争取把每一个合数用它的某一个质因子筛掉

数据范围为 10^7 线性筛法会比埃氏筛法快一倍左右

时间复杂度为线性

素数筛(线性筛法)_Wansit的博客-CSDN博客_线性素数筛

通过观察上面的埃氏筛，我们可以发现其实存在重复标记的情况，例如 6 这个数字，在2的时候会被标记一次，在 3 的时候也会被标记一次，故欧拉筛，也叫线性筛，保证了每个合数只被最小的质因数筛掉，即每一个合数只会被标记一次 

#include 
#include 
using namespace std;

const int N = 1000010;

int primes[N],cnt;
bool st[N];

void get_primes(int n) 
{
	//从 2 到 n 枚举
    for(int i = 2;i <= n;i++ )
    {
        //如果是质数就把它加到质数表里面去
        if(!st[i]) primes[cnt++] = i;
        //从小到大枚举所有的质数 
        for(int j = 0;primes[j] <= n / i/* primes[j] * i <= n */;j++ ) 
        {
            //primes[j]是从小到大枚举的所有质数 每次筛掉当前质数 primes[j] * i 
            st[primes[j] * i] = true;
            //primes[j]一定是i的最小质因子 不管什么情况,primes[j]一定是 primes[j] * i 的最小质因子
            if(i % primes[j] == 0) break; 
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;    

    return 0;
}

n = 10^6 的范围下，线性筛法运行时间为 45 ms 和埃氏筛法差不多

n = 10^7 的范围下，线性筛法比埃氏筛法快一倍左右

线性筛法

埃氏筛法

竖着看乘数是 2 ~ 22，22 就是 45 / 2 那个数，只需要让 i ++ 循环即可

被乘数一定是小于等于后面那个数，并且是最小质因子

对于 2 而言，乘数是 2，前面只有 2

对于 3 而言，比它小的质数就是 2、3

对于 5 而言，比它小的质数就是 2、3、5

考虑了 2 × 4，为什么没有考虑 3 × 4？难道 3 不是比 4 小的质数吗？因为 3 × 4 的最小质因子是 2，在 2 × 6 的时候被筛掉了

所以考虑一下被乘数到什么时候停止呢？到达这个乘数必然会停止的，如果这个乘数是质数，前面的数肯定不会是它的因子，到达这个乘数就结束；如果这个乘数是合数，前面这个数到什么时候停止呢？例如 4 是 2 的倍数的时候就停止

        2        ×        5

        3        ×        5

        5        ×        5

primes[ j ]  ×         i

接下来看一下线性筛法为什么是线性的？原理是什么？

n 只会被它的最小质因子筛掉

j 在筛选的时候是从小到大枚举所有的质数，每次把当前的质数和 i 的乘积筛掉

线性筛法解析_士女士女子的博客-CSDN博客_线性筛法

任何一个合数一定会被筛掉，任何一个数 x 一定有且只有一个最小质因子，所以每个数只会被筛选一次，所以是线性的

首先需要判断 i 是质数还是合数，如果是质数就将它放入primes[ ] 数组。

在第二个for循环中，将primes[ j ]的 i 倍筛掉（i 是从小到大依次遍历）

若存在一个合数X，设primes[ j ] 是它的最小质因子，当 i 枚举到X之前，一定会先枚举到X / primes[ j ]，而在那时，就已经先将X筛掉了。所以任何一个合数一定会被筛掉，是因为我们只用最小质因子来筛，但每个数只有一个最小质因子，所以每个数都只会筛一遍。例如 X = 12，2是 12 的最小质因子，在枚举到 12 之前一定会先枚举到 6，并执行了st[ 2 * 6 ] = true，所以 i == 12 时，不会进入primes[ j ]数组

最后的 if 语句有两种情况：

（1）若 i % primes[ j ] == 0 ，则说明 primes[ j ] 是 i 的最小质因子，那么primes[ j ] 也一定是primes[ j ] * i 的最小质因子。例如：4 % 2 == 0 ，2 是 4 的最小质因子，且 2 也是2 * 4 的最小质因子。

（2）若i % primes[ j ] != 0 ，由于我们是从小到大枚举的所有的质数，并且我们没有枚举到 i 的任何一个质因子，则此时primes[ j ] 一定小于 i 的所有质因子，但是primes[ j ] 也一定是primes[ j ] * i 的最小质因子。

例如：9 % 2 ！= 0，2 一定小于 9 的最小质因子，但 2 一定是 2 * 9 的最小质因子。（ 9 的最小质因子是3，9 要枚举到 3 才break，但 9 * 2 的最小质因子是 2，当枚举到 2 时就可以 break ）