筛法
EDG_AKUYTRE
·
·
个人记录
筛法
引入
如果我们想要知道小于等于
n 有多少个素数呢？
一个自然的想法是对于小于等于
n 的每个数进行一次质数检验。这种暴力的做法显然不能达到最优复杂度。
1.埃拉托斯特尼筛法
过程：
考虑这样一件事情：对于任意一个大于
1 的正整数
$x $倍就是合数$（
x > 1）$。利用这个结论，我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
优化：
1.要找出$ 1∼n $的所有质数，只需要对 1∼$sqrt(n)$的质数进行筛选就够了。正确性显然。
2.对于一个质数 $ p $，只需从它的 $ p $ 倍开始标记即可，因为 $ 2∼p−1 $ 倍已经被前面的质数标记了。
例如：
当i=5时，5×2=10已被i=2筛过
5×3=15已被i=3筛过
5×4=20已被i=2筛过
```cpp
void solve(int n){
memset(is_p,true,sizeof(is_p));
is_p[0]=is_p[1]=0;
for(int i=2;i*i<=n;i++){
if(is_p[i]){
for(int j=i*i;j<=n;j+=i){
is_p[j]=false;
}
}
}
}
```
以上为 Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法），时间复杂度是
$O(n\log\log n)$。
2.线性筛法
```
void euler(int n){
memset(is_p,1,sizeof(is_p));
is_p[0]=is_p[1]=0;
for(int i=2;i<=n;i++){
if(is_p[i])prime[++cnt]=i;
for(int j=1;j<=cnt && (long long)i*prime[j]<=n;j++){
is_p[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
}
```
基本思想与原理：
初始化：
创建一个 bool 类型的数组 is_prime[]，初始标记所有数为 true。
维护一个质数列表 Prime，用于动态存储已发现的素数。
筛选过程：
遍历每个整数 i 从 2 到 n：
若 i 是素数，将其加入 Prime 列表。
对当前已知的所有素数 p
j
：
计算合数 m=i×p
j
。
若 m>n，终止内层循环。
将 m 标记为合数。
关键步骤：若 i 能被 p
j
整除，终止内层循环。
上面的这种 线性筛法 也称为 Euler 筛法（欧拉筛法）。
板子p3383
---
题目：
1.P3927
我们看到转换进制的题目，首先想到的肯定是短除法做，很容易的就会发现，末尾有多少个 0，也就是能整除 K 的多少次方。(根据进制的意义，在k进制的情况下逢k进1，那么末位就变为了0。)
于是问题转化为 n! 能够整除 K 的几次方。
n! 必然是一个天文数字，于是我们想到唯一分解定理，把 n! 和 K 都分解成质数相乘的形式，再用 n! 和 K 所包含的 K 的质因数的次数相除，取最小值就得到了答案了。
有人就问了，哎你那个 n! 的质因数你也求不出来啊。其实这是没有必要的，前面说过，只要求 n! 和 K 所包含的 K 的质因数的次数相除就可以了，所以我们只需要求出 K 的质因数来就可以了。
那么怎么求 n! 中那些质因数的次数呢? 由于 n! 是从 1 一直乘到 n，所以每 p 个数里就有一个质数 p，所以我们只要用 n 一直除以 p 就可以了.
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN=2e5+10;
int n,k;
int p[MAXN],c[MAXN],ans;
int cnt;
signed main(){
cin>>n>>k;
for(int i=2;i*i<=k;i++){
if(k%i==0){
p[++cnt]=i;
c[cnt]=0;
while(k%i==0){
++c[cnt];
k/=i;
}
}
}
if(k>1){//若k是素数
p[++cnt]=k;
c[cnt]=1;
}
ans=1e18;
for(int i=1;i<=cnt;i++){
int t=0,now=n;
while(now)t+=now/=p[i];// 计算n!中包含质因数p[i]的总次数
t/=c[i];//用总次数除以k中该质因数的次数
ans=min(ans,t);
}
cout<<ans;
return 0;
}
```
2.B4272
1.预处理质因数个数：使用筛法预处理1到M范围内每个数的质因数个数
2.统计最大值：遍历N到M范围，找出质因数个数的最大值
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=1e7+5;
int p[MAXN];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
//筛法预处理每个数的质因数个数
for(int i=2;i*i<=m;i++) {
if(p[i]==0){// i是质数
for(int j=i*i;j<=m;j+=i) {
int num=j;
while(num%i==0){//计算j中包含多少个i因子
p[j]++;
num/=i;
}
}
}
}
//找出N到M范围内的最大值
int ans=0;
for(int i=n;i<=m;i++)
ans=max(ans,p[i]);
cout<<ans<<endl;
return 0;
}
```
感谢oiwiki与题解区，还有题目评论区