#M8403. C4.03 质数筛
C4.03 质数筛
质数
质数(也称为素数)是指在大于 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 整除时,就停止这个内层循环。这一步是关键,它保证了每个合数只会被它的最小质因数筛除。