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

数论

组合计数

高斯消元

简单博弈论

质数的定义、质数的判定

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

第十二届蓝桥杯省赛第二场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 <iostream>
#include <cstdio>
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) 基本上是一个级别的

#include <iostream>
#include <cstdio>
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博客_线性素数筛

#include <iostream>
#include <cstdio>
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;
        //从小到大枚举所有的质数 当质数大于 n / i break
        for(int j = 0;primes[j] <= n / i;j++ ) 
        {
            //筛掉primes[j] * i 不管什么情况 primes[j] 一定是 primes[j] * i 的最小质因子
            //一定是用这个数的最小质因子去筛选这个数
            st[primes[j] * i] = true;
            //primes[j]一定是i的最小质因子 primes[j]是从小到大枚举的所有质数
            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 的范围下，线性筛法比埃氏筛法快一倍左右

线性筛法

埃氏筛法

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

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

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

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

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

最后的 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 ）