title: 素数筛
date: 2022-11-16 12:41:47
tags: 算法
本文章遵守知识共享协议 CC-BY-NC-SA ，转载时需要署名，推荐在我的个人博客阅读。
大意
素数筛是一种快速在 $[1,n]$ 区间中判断素数 / 求出第n个质数的方法。
讲解
首先是判断质数的函数，时间复杂度为 $O(\log n)$
这样查询的话，判断 $[1,n]$ 质数数量 / 第 $n$ 个素数 的复杂度就是 $O(n \log n)$，在样例达到一定程度时会超时。
bool isprime(int t){
if(t<=2) numurn false; // 小于2肯定不是
for(int i=2;i<=sqrt(t);i++) // 枚举 1 ~ 根号t，可以加速代码
if(t%i==0) // t有除了1和自己以外的约数
numurn false;
numurn true;
}
这样的思路其实是有问题的。我们如果要一次性查询大量素数，就需要一次性处理，减少重复运算，这样才能增加效率。
void get_prime(int n)
{
for (int i = 2; i * i <= n; i++)
if (!prime[i]) // 是素数，加速运算
for (int j = i * i; j <= n; j += i)
prime[j] = 1; // 不是素数，标记
}
上面的代码时间复杂度为 $O(\log^2n)$ ，虽然复杂度非常优秀，但是还是没有达到线性水平。
接下来，请出今天的主角————欧拉素数筛。
不要看他有多层循环，实际上复杂度仍为 $O(n)$。
void ola_prime(int n){
for(int i=2;i<=n;i++){
if(!check[i])
prime[++cnt]=i; // 标记这是第i个质数
for(int j=1;j<=cnt;j++){ // 枚举已经求出来的质数
if(i*prime[j]>n)break; // 大于范围就退出
check[i*prime[j]]=1; // 标记不是质数
if(!(i%prime[j]))break; // 重点，下面会讲
}
}
numurn;
}
在上面的代码中，有一行代码非常重要，如果没有它，时间复杂度不可能达到 $O(n)$ 。
就是这一行
if(!(i%prime[j]))break; // 重点，马上讲
因为 $i$ 模上 $prime_j$ 已经等于 $0$ 了，代表接下来的数已经被筛过了，所以直接跳过（我也不会证明）。
模板题目
P3383-【模板】线性素数筛
纯粹的模板题目，应该不用说。
1622:Goldbach’s Conjecture
先预处理 $[1,10^6]$ 之间的素数，然后转化问题。
因为 $b-a$ 最大， $n=a+b$ ，则可以得到 $a$ 应该是最小的。
所以只要求满足 $prime_a$ 和 $prime_n-a$ 都是素数，且 $a$ 最小。
核心代码
for (int i = 2; i <= primecnt; i++) // 直接遍历id
if (!bits[i] && !bits[num - i]) // 满足上述条件
{
printf("%d = %d + %d\n", num, i, num - i); // 输出
break; // 找到就退出
}
P1835-【模板】素数密度
合数的一个小性质： 令合数 $p = ab (0 \le a,b)$ 则 $\min(a,b) <= \sqrt{p} $
所以我们只处理 $\sqrt{2^{31}}$ ，然后对于每个质数 $p$ ，求出最小的一个 $[l,r]$ 间的数可以被 $p$ 整除，然后 $start+p,start+2p,start+3p,...start+np$ 都是质数。
注意! $start$ 至少应该为 $2p$，因为 $p$ 是质数。
for (long long i = 1; i <= primecnt; ++i){
long long p = prime[i], start = ((l + p - 1) / p) * p;
if (start < 2 * p)
start = 2 * p;
for (long long j = start; j <= r; j += p)
book[j - l + 1] = 1;
}
【没有例题链接】求约数个数
给定 $n$ ，求 $n$ 的约数个数
首先定义 $sum_i$ 为 $i$ 分解质因数后最小质数的次方数+1。
为什么要+1呢？因为根据约数个数定理（假设 $n$ 被分解为 $\prod_{i \in p}{p_i^{c_i}}$），就可以分解为以下形式。
$$ sum(n) = \prod_{i \in p}{(c_i+1)} $$
定义 $num_i$ 为 $i$ 的约数个数。
若 $p$ 为质数，可以得到 $sum_i$ 为 $1$
下面是示例代码：
void solve(){
check[1]=1;
num[1]=1; // 约数个数
sum[1]=1;
for(int i=2;i<=size;i++){
if(check[i]==0){
prime[++cnt]=i;
num[i]=2; // 约数个数
sum[i]=2; //
}
for(int j=1;j<=cnt;j++){
if(i*prime[j]>size)break;
check[i*prime[j]]=1;
if(i%prime[j]==0){ // 如果可以整除
sum[i*prime[j]]=sum[i]+1; //
num[i*prime[j]]=(num[i]/sum[i])*sum[i*prime[j]]; //
break;
}
else{
sum[i*prime[j]]=2; // i 与 p 互质
num[i*prime[j]]=num[i]*sum[i*prime[j]]; //
}
}
}
}