前言
本文写于 email 同学被巨水的素数筛教做人之后.
会提到两种筛法: 埃拉托色尼筛法, 线性筛法.
知识储备
1. 对于一个合数 x, 必有一个范围在 2~x 的因数.(显然)
2. 任何一个大于 1 的自然数都能被唯一分解有限个质数的乘积, 如 X=P1 a1 *P2a2 *......* Pn an 其中 P 为质数, a 为指数.
素数的判定(试除法)
字面意思, 根据第一条性质, 我们枚举 2~~n 所有数, 用 n 去试着除以, 若有能整除的 n 为合数, 若都不能整除, n 就是质数了.
- int prime(int n)
- {
- for(int i=2;i*i<=n;i++)
- if(!(n%i))
- return 0;
- return 1;
- }
时间复杂度 O:(n)
埃拉托色尼筛法(Eratosthenes)
这种筛法应该是是效率相对比较高, 而且很好理解, 用得最多的筛法.
试除法是用原数去尝试诸多因子, 那对于求一个范围 (比如 1~N) 的所有素数, 显然上述方法是不可取的.
那我们反向思考, 尝试枚举因子去排除素数(即标记合数).
枚举 2~N, 并且用 2~N 的倍数去标记合数, 比如枚举到 i, 那 2*i,3*i,4*i......, 全部都标记为合数, 直到 k*i>N.
扫到数 x 时, 看它是否有合数标记, 如果没有, 则说明 2~x-1 的数中, 都没有它的因数, 根据性质 1, 显然 x-1>x(x>2), 所以 x 为质数.
显然, 一个合数可能被多个小因数标记, 这就是优化的下手处.
我们如果不从 2*i 开始筛, 而从 i*i 开始筛是否可行呢?
显然可行. 因为我们扫到 2 的之后就已经用 2 筛完了所有 2 的倍数, 扫到 3 的之后已经筛完了所有 2,3 的倍数, 扫到 4 的之后已经筛完了所有 2,3 ,4 的倍数......
所以扫到 i 时, 2~i-1 的倍数已经全部被筛了, 没必要再筛 i 的 2~i-1 倍的数, 可以直接从 i2 开始筛了.
- void primes(int n)
- {
- memset(v,0,sizeof(v));// 假设全是素数, 无合数标记
- for(int i=2;i<=n;i++)
- {
- if(!v[i])
- {
- prime[++cnt]=i;
- for(int j=i*i;j<=n;j+=i)
- v[j]=1;
- }
- }
- }
时间复杂度: O( N/p ) =O(N loglogN ),p 为小于 N 的质数 . 接近线性效率, 而且比较起线性筛是更灵活的(最后的例题会提到)
线性筛法
优化后的埃拉托色尼筛也有重复筛到数的情况, 比如 2,3 都会筛 12,2 和 4 都会筛到 24, 要保证线性效率, 就必须让每个数只被筛一次
我们不能让 12=2*6,12=3*4 发生, 只能让 12=2*2*3 发生.
所以我们需要将每个合数用它最小的质因子筛去.
标记合数时, 我们只向现有的数中乘上一个质因子, 这相当于合数的质因子从小到大累积.(意思是现在只能用现在扫到的这个数乘筛出来的素数来筛后面的素数)
因为找出筛的素数一定是最小素数, 所以对于扫到的合数, 它只能筛到出现它的约数之前的数的它的倍数. 质数则能筛掉 2*x~x*x.(小于 x2 的所有 x 的质数倍)
前面说得太抽象了, 不理解不要紧, 模拟一下.
prime[]数组装素数, v[i]是筛掉 i 的那个最小质因数, 若无标记说明是质数
1, 扫到 2,v[2]无标记, 赋值 :v[2]=2,prime[1]=2.
遍历 prime, 用 2*prime[j], 可以筛掉 4. 赋值: v[4]=2.
2, 扫到 3,v[3]无标记, 赋值: v[3]=3,prime[2]=3.
遍历 prime, 用 3*prime[j], 可以筛掉 6,9 . 赋值: v[6]=2,v[9]=3
3, 扫到 4,v[4]有标记
遍历 prime, 用 4*prime[j], 只能筛掉 8, 赋值: v[8]=2(不能筛 12!! 即便有 3 这个素数. 因为 3 大于 4 的最小质因数 2 了, 用 3*4 筛就违背了 2*3*3 的原理, 这里能被 3*4 筛掉的 12, 后来也可以被 2*6 筛到, 保证了筛到 12 的是最小质因数 2)
4, 扫到 5,v[5]无标记, 赋值: v[5]=5,prime[3]=5.
遍历 prime, 用 5*prime[j], 可以筛掉 10,15,25 . 赋值: v[10]=2,v[15]=3,v[25]=5,
大概就是这样了
- void primes(int n)
- {
- memset(v,0,sizeof(v));// 假设全是素数, 无合数标记
- for(int i=2;i<=n;i++)
- {
- if(!v[i])
- {
- prime[++cnt]=i;
- v[i]=i;
- }
- for(int j=1;j<=cnt;j++)
- {
- if(prime[j]>v[i]||prime[j]*i>n)break;
- // 出现了比 i 的最小质因数还小的质数(对于 4 来说出现了 3)
- v[prime[j]*i]=prime[j];
- }
- }
- for(int i=1;i<=cnt;i++)
- cout<<prime[i]<<" ";
- }
例题
题意
求出范围 [k,n] 内的合数个数, 并且求出筛掉每个合数的最小素数之和, 答案对 998244353 取模
数据规模
分析
数据规模 1e12 太大了, 线性筛也无法处理, 但是区间大小只有 1e7, 所以我们可以用线性筛 + 埃拉托色尼筛
用线性筛预处理出 1e6 范围内的所有素数, 再用这些素数去做埃拉托色尼筛.
为什么不能都做线性筛? 因为线性筛必须完全记录了筛每一个数的那个素数, 不能有任何无操作的空白, 而埃拉托色尼筛就没有这类限制, 比较灵活, 直接把筛出来的素数用来继续筛.
注意数组开不下, 需要移一下位.
- #include<bits/stdc++.h>
- using namespace std;
- #define N 10000100
- #define ll long long
- const ll limit=2000000;
- const ll mod=998244353;
- ll prime[N],v[N];
- ll n,k,cnt,ans1,ans2;
- int main()
- {
- cin>>k>>n;
- for(ll i=2;i<=limit;i++)
- {
- if(!v[i])
- {
- v[i]=i;
- prime[++cnt]=i;
- }
- for(ll j=1;j<=cnt;j++)
- {
- if(prime[j]>v[i]||prime[j]*i>limit)break;
- v[prime[j]*i]=prime[j];
- }
- } // 线性筛预处理
- memset(v,0,sizeof(v));
- for(ll i=1;i<=cnt;i++)
- {
- ll st=max((ll)1,(k-1)/prime[i])*prime[i]+prime[i];// 计算出起始位置
- for(ll j=st;j<=n;j+=prime[i])
- {
- if(!v[j-k])
- {
- v[j-k]=1;
- ans1++;
- ans2=(ans2+prime[i])%mod;
- }
- }
- }
- cout<<ans1<<" "<<ans2;
- return 0;
- }
总结
关于素数筛的整理到此告一段落, 比较基础的知识, 两种筛法各有好处, 线性筛更快, 但是埃拉托色尼筛可以节约空间, 也比较适合做区间的跨度不大, 但区间本身左右端点数值很大的题目.
来源: https://www.cnblogs.com/NSD-email0820/p/9490828.html