[算法练习笔记] 5、筛质数 + 前缀和解决 非素数个数问题

一、筛质数算法

名词解释：
质数： 只有1和它本身两个因数（约数），那么这样的数叫做质数，也叫素数。
合数： 除了能被1和它本身整除，还能被其他的正整数整除，那么这样的数叫做合数。
筛质数： 将筛选范围内的质数全部筛选出来
待查区间：1 ~ n

筛选方法如下：

1、最简单筛质数法

也就是枚举从2 ~ n的所有数，一个个来判断是否为质数。
时间复杂度约为O(n²)，最劣。

关键代码

for(int i=1;i<=n;++i)     //枚举1到n
{
    bool flg=0;
    for(int j=2;j<i;++j)  //枚举2到i
    {
        if(i%j==0)        //如果i%j=0,也就是i已经不为素数了
        {
            flg=1;        //打上标记
            break;        //跳出循环，不用再枚举了
        }
    }
    if(flg==0)            //如果没有被打上标记
    prime[i]=1;           //prime来标记这个数是否为素数。
}

2、最简单筛质数法的优化

研究知道，在判断质数的时候，不一定需要枚举到 i − 1，只需要枚举到 √i就可以判断出来了。
因为约数是成对出现的，比如12，你找到一个约数是3，那么另一个约数就是4；其次，这两个约数一定一个小于√n，一个大于√n，因为都在√n之前的话，相乘一定会小于n（因为√n * √n = n），而两个约数都在√n后，则相乘一定会大于n，
所以，如果你在√之前找不到约数，那么√n之后一定没有，此时这个数就一定是质数。
时间复杂度约为O(n * √n)。

关键代码

for(int i=1;i<=n;++i)        //枚举1到n
{
    bool flg=0;
    for(int j=2;j*j<=i;++j)  //枚举2到i
    {
        if(i%j==0)           //如果i%j=0,也就是i已经不为素数了
        {
            flg=1;           //打上标记
            break;           //跳出循环，不用再枚举了
        }
    }
    if(flg==0)              //如果没有被打上标记
    prime[i]=1;             //prime来标记这个数是否为素数。
}

3、暴力筛质数法

i从2开始枚举，一直到n，将i的倍数标记，标记后即为合数。
时间复杂度：约为O(nlogn)。

int primes[N], cnt; // primes[]是用来存储所有素数
                    // cnt == count 总数的意思，用来当计数器
                    // 全局变量和数组默认初始化为0
bool st[N]; // st[x]存储x是否被筛掉，0表示是质数，1表示是合数被筛掉了

// 最简单筛质数
void get_primes(int n)  
{
    for (int i = 2; i <= n; i ++ ) // 从2开始筛，看是不是质数
    {
        if (!st[i]) // 即st[i]是0，是质数
        {
            primes[cnt ++] = i; // 将素数数组对应位置置为i
        }
         // 再将每一个数的倍数筛掉
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

4、朴素筛质数法（埃氏筛法）

与最简单筛法的区别：筛掉数的倍数时，只筛掉质数的倍数，不再筛合数的倍数
此时的时间复杂度约在O(nlog(logn)) 也就是约等于O(n)。
首先，定义 st[i]数组表示 i 是否为质数，primes[i]储存已经找到的所有质数，cnt储存当前一共找到了多少质数。

int primes[N], cnt; // primes[]是用来存储所有素数
                    // cnt == count 总数的意思，用来当计数器
                    // 全局变量和数组默认初始化为0
bool st[N];         // st[x]存储x是否被筛掉，0表示是质数，1表示是合数被筛掉了

// 埃氏筛质数
void get_primes(int n)  
{
    for (int i = 2; i <= n; i ++ ) // 从2开始筛，看是不是质数
    {
        if (!st[i])               // 即st[i]是0，是质数
        {
            primes[cnt ++] = i;   // 将质数数组对应位置置为i
            // 再将每一个质数的倍数筛掉
            // (此步不筛掉合数的倍数，是因为合数可以被分解质因数，所以在前面已经被筛掉了)
        	for (int j = i + i; j <= n; j += i) st[j] = true;
        }
        // 如果for在这，则时间复杂度约为n(nlogn)。
    }
}

5、线性筛质数法

我们发现，埃氏筛已经很快了，但是还是有所不足。
因为在埃氏筛中，有很多数有可能被筛到很多次（例如 6 , 他就被 2 和 3 分别筛了一次）。所以在欧拉筛中，
我们就是在这个问题上面做了优化，使得所有合数只被筛了一次。
如果当前已经枚举到了i。如果 st[i]=1 ，也就是i为质数。则 primes [cnt+1]=i，将这个质数i存到primes数组中
然后我们每一次枚举都要做这个循环: 枚举 j从 1到 cnt。stprimesj×i= 0（因为 primesj 为质数，i就表示这个数的多少倍，
要把他筛掉）。

注意，接下来是重点：

如果 i mod primes[j]=0，跳出第二层循环，为什么是i % primes[j] == 0时呢？
当i % primes[j] = 0的时候如果不中止，那么将进入下一次循环，下一次循环要筛掉的数字是primes[j + 1] * i。
对于primes[j + 1] * i来说，i并没有改变，那么i此时仍然满足上一步所完成的i % primes[j] = 0，即primes[j]当前
仍然是i的最小质因数，能整除i。 则primes[j + 1] * i这个数一定是primes[j]这个质数的倍数，在primes[j] * i时
已经被找出并筛掉了。所以，此时的primes[j + 1] * i再次进行判定然后被筛掉这个过程显然是重复的，就增加了时间
开销，所以当i % primes[j] = 0时，循环就可以退出了，此时已经筛出了质数primes[j]的所有倍数。
由于所有的合数从小到大只被筛了一次，这个过程是线性的，所以这种方法叫做线性筛质数法，时间复杂度约为O(n)。

int primes[N], cnt;                 // primes[]存储所有素数  注：prime n.质数，素数
bool st[N];                         // st[x]存储x是否是素数，初始全部为false
st[1]=0;                            // 令i = 2时，数组值为1，表示是素数

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )        // 主要目的是为了筛出2 ~ n的所有质数
    {
        if (!st[i]) primes[cnt ++ ] = i;  // 若st[i]没有被筛掉，说明是质数
        for (int j = 0; primes[j] * i <= n; j ++ )  // 枚举从0开始，最大到cnt所有数 
        {
            st[primes[j] * i] = 1;         // 表示primes[j]的所有倍数都是合数 
            if (i % primes[j] == 0) break; // 已经筛出了primes[j]的所有倍数
        }
    }
}

若 n < 10⁶ 时，线性筛和埃氏筛的时间效率差不多; 若 n > 10⁷ 时，线性筛会比埃氏筛快了大概一倍。

二、前缀和算法

前缀和算法，顾名思义，求的是某个数组的前m ~ n项之和，可以用数学中数列的前n项和来理解。
以求数组S[i]至S[j](j > i)的前缀和为例，运算过程即：
S[i]至S[j](j > i)的前缀和 = S[0] ~ S[j]之和 减掉 S[0] ~ S[i]之和。
注意需要定义S[0] = 0，目的是统一前缀和的求法，使得无论是求S[i]至S[j](j > i)的前缀和，还是仅求S[j]的前缀和(=S[j] – S[0])，运算过程都是S[j] – S[?]，重在理解这种统一处理的思想。

核心代码

	for (int i = 1; i <= n; i ++ )
	{
         s[i] = s[i - 1] + a[i]; // 前i项和 = 前i - 1项和 + 第i项值
    }

三、筛质数 + 前缀和解决问题

题目描述

求 [a,b]之间的合数个数。

注意，1既不是质数，也不是合数。

输入格式
输入包含多组测试数据。
每组数据占一行，包含两个整数 a,b。

输出格式
每组数据输出一行答案，表示合数的个数。

数据范围
1 ≤ a ≤ b ≤ 10⁷,输入最多包含 10组数据。

输入样例：
1 10
1 100
输出样例：
5
74

解题思路

本题原理上来说是最简单的找素数问题，只是如果用暴力枚举方法筛选的话时间复杂度会在O(n²)量级，而本题的运算规模
和时间要求时O(n)量级，所以在执行主函数前，需要先用线性筛质数法(O(n))预处理找到所有的合数，再用前缀和思想找到从a到b之间的所有合数即非素数即可。

解题代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;      // 题目要求10的7次方，多开10个位置防止数组越界
int primes[N], cnt, s[N];    
bool st[N];                  // 线性筛法所需条件

void get_primes(int n)  
{
    // 线性筛质数预处理
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; j ++ ) 
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
    
    // 前缀和预处理
    for (int i = 2; i <= n; i ++ )
    {
        s[i] = s[i - 1];           // 统计前i项的合数的数量
        if (st[i]) s[i] ++;        // 如果st[i] = 1表示是合数，s[i]的值就 + 1
    }
}

int main() {
    int a, b;
    get_primes(N - 1);             // 预处理
    while (cin >> a >> b)          // 循环输入数据，这种写法值得借鉴
    {
        cout << s[b] - s[a - 1] << endl;
    } 
}

参考文献

1、AcWing 969 筛质数：https://www.acwing.com/activity/content/code/content/5374176/
2、洛谷：https://www.luogu.com.cn/blog/Bqianyi/zhi-shuo-shai
3、基础算法 前缀和：https://zhuanlan.zhihu.com/p/117569086
4、题目来源：AcWing 3701. 非素数个数 https://www.acwing.com/problem/content/3704/
5、https://blog.csdn.net/lx1056212225/article/details/125009857