质数

质数（也称为素数）是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。

例如：
2、3、5、7、11 等都是质数。相反，能被其他数整除的数称为合数，比如 4（能被 2 整除）、6（能被 2 和 3 整除）等。
2 最小的质数是，它是唯一的偶质数。这是因为大于 2 的偶数都能被 2 整除，所以不是质数。

质数判断

试除法：对于一个数 n，从 2 开始，依次用小于等于 sqrt(n) 的数去除 n，如果都不能整除，那么 n 就是质数。

bool isPrime(int n)
{
    // 如果 n 小于 2，不是质数，直接返回 false
    if (n < 2) return 0;
    // 从 2 开始遍历到根号 n
    for (int i = 2; i * i <= n; i++)
    {
        // 如果 n 能被 i 整除，说明 n 不是质数，直接返回 false
        if (n % i == 0) return 0;
    }
    // 如果经过上述循环没有返回 false，说明 n 是质数，返回 true
    return 1;
}

Warning！

试除法一般用于判定一个数是否为质数，如需批量找出一定范围内的质数效率不高。

埃拉托斯特尼筛法(简称：埃氏筛)

基本思想：

一个质数的倍数(倍数为 1 除外)肯定是合数，那么我们利用这个性质数算出合数。

从 2 开始，将每个质数的 x 倍数(x > 1)，标记为合数(即非质数)，直到指定范围内的所有数标记完。

这样，未被标记的数就是质数。其实合数的倍数也是合数，只是重复标记没有意义。

埃氏筛_参考代码

// 定义一个常量 N，表示数组的大小上限为 100001
const int N = 1e5 + 1; 
// 定义一个布尔类型的数组 temp，用于标记每个数是否为质数
bool temp[N];

void isPrime(int n)   
{
	// 将数组的第 0 个和第 1 个元素标记为非质数（1 表示非质数）
    temp[0] = temp[1] = 1;
    
    // 从 2 开始遍历到根号 n
    for(int i = 2; i * i <= n; i++)
    	// 如果当前数 i 未被标记为非质数
        if(temp[i] == 0)
        	// 以 i 为起点，遍历直到 j * i 大于等于 n
            for(int j = i; j * i <= n; j++)
            	// 将 i 的倍数标记为非质数
                temp[j * i] = 1; 
}

埃氏筛_代码解析

假设要找出小于等于 n 的所有质数。首先创建一个长度为 n + 1 的布尔数组（初始值都设为 false），用来标记每个数是否为质数。将索引为 0 和 1 的元素设为 true，因为 0 和 1 不是质数。

从 2 开始，当找到一个值为 false 的数 i 时，它就是质数。然后将 i 的倍数（从 2i 开始，小于等于 n）对应的数组元素设为 true，因为这些数是合数。

重复这个过程，直到遍历完所有小于等于的数。最后，数组中值为 false 的索引对应的数就是质数。

线性筛/欧拉筛

基本思想：

欧拉筛(线性筛)是一种改进的素数筛选法，其核心思想是每个合数只被它的最小质因数筛一次，避免了重复标记的问题，提高了效率。

线性筛/欧拉筛_参考代码

// 定义一个常量 N，表示数组的大小上限为 100000001
const int N = 1e8 + 1;
// 定义一个布尔类型的数组 temp，用于标记每个数是否为质数（初始时假设都是质数）
bool temp[N];   
// 定义一个整数数组 p，用于存储找到的质数；定义整数 k，用于记录找到的质数个数
int p[N], k;

void prime(int n)  
{
	// 将 0 和 1 标记为非质数（因为 0 和 1 不是质数）
    temp[0] = temp[1] = 1; 
    
    // 从 2 开始遍历到 n
    for(int i = 2; i <= n; i++)
    {
    	// 如果当前数 i 未被标记为非质数，说明 i 是质数
        if(temp[i] == 0)
        	// 将 i 存储到质数数组 p 中，并增加质数个数 k
            p[k++] = i;
        
        // 遍历已找到的质数数组 p
        for(int j = 0; j < k && p[j] * i <= n; j++)   
        {
        	// 将质数 p[j] 与 i 的乘积标记为非质数
            temp[p[j] * i] = 1;  
            // 如果 i 能被 p[j] 整除
            if(i % p[j] == 0)  
            // 跳出内层循环，因为此时再继续遍历已无意义，后面的质数与 i 的乘积也能被 p[j] 整除
                break;
        }  
    }  
}

线性筛/欧拉筛_代码解析

同样要找出小于等于 n 的所有质数，创建一个布尔数组 temp[n + 1]（初始值都设为 false），用于标记每个数是否为质数，将 0 和 1 标记为 true。同时创建一个数组 p，用于存储筛选出的质数。

从 2 开始遍历到 n，对于每个数 i，如果 temp[i] 为 false，则将 i 添加到 p 中。

然后对于 p 中的每个质数 prime，计算 i * prime，只要 i * prime 小于等于 n，就将 temp[i * prime] 设为 true。并且当 i 能被 prime 整除时，就停止这个内层循环。这一步是关键，它保证了每个合数只会被它的最小质因数筛除。