专栏文章

筛法

EEDG_AKUYTRE
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mionx9oi
此快照首次捕获于
2025/12/02 22:17
3 个月前
此快照最后确认于
2025/12/02 22:17
3 个月前
查看原文

筛法

引入

如果我们想要知道小于等于 n 有多少个素数呢？ 一个自然的想法是对于小于等于 n 的每个数进行一次质数检验。这种暴力的做法显然不能达到最优复杂度。

1.埃拉托斯特尼筛法

过程：
考虑这样一件事情：对于任意一个大于 1 的正整数 nn，那么它的 xx 倍就是合数（x>1）（ x > 1）。利用这个结论，我们可以避免很多次不必要的检测。 如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
优化：
1.要找出1∼n1∼n的所有质数，只需要对 1∼sqrt(n)sqrt(n)的质数进行筛选就够了。正确性显然。
2.对于一个质数 pp，只需从它的 pp 倍开始标记即可，因为 2∼p−12∼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(nlog⁡log⁡n)O(n\log\log n)。
2.线性筛法
CPP
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 就可以了.
CPP
#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与题解区，还有题目评论区

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...