2026年8月30日（筛法）
2026-08-30 11:04:05
发布于：广东
//埃氏筛，线性筛
//判断质数/寻找质数
//质数/素数 对于一个整数x，除了1和本身以外不能够被其他任何>1的整数整除的数字
//O(x)
int a[N];//默认全部都是0/false
//埃氏筛 Nlog*log
//线性筛，每个数字只标记一次
void prime(int n){
a[0]=a[1]=true;//true表示为非质数
for(int i=2;i<=n;i++){
if(a[i]==true)continue;
for(int j=2;j*i<=n;j++){
a[i*j]=true;
}
}
}
//暴力O(sqrt(x))
bool is_prime(ll x){//判断x是否是质数
if(x<=1)return false;
for(int i=2;i<=sqrt(x);i++){
for(int i=2;i*i<=x;i++){//更推荐
for(int i=2,len=sqrt(x);i<=len;i++){
if(x%i==0)return false;
}
return true;
}
a[N];
for(int i=1;i<=n;i++){//nsqrt(n)//1e9
a[i]=is_prime(i);
}
//质数 合数
// 对于任何一个合数，至少被拆解为几个质数乘积的形式
//至少两个
8=2*2*2
24=2*2*2*3
//假设一个合数x被拆解为a*b的形式
//问min(a,b)的最大可能是多少
24=1*24/2*12/3*8/4*6
x=a*a;
a^2=x;
a=sqrt(x);
24=1 2 3 4 6 8 12 24//具有对称性
9=1 3 9
//x
for(int i=1;i<=x;i++){
if(x%i==0)cout<<i<<' ';
}
for(int i=1;i<=sqrt(x);i++){
if(x%i==0)cout<<i<<' ';
if(x/i!=i)cout<<x/i<<' ';
}
//给定一个数字x，判断x因数个数的奇偶性
//只有当x为完全平方数的时候，x的因子个数为奇数个
埃氏筛:Nloglog
//2^10=1024
//log(2,1024)=10;
缺点
1.必须从小开始往大推
2.对于合数会被重复标记
线性筛:O(n)
核心思想，找合数
24=2 3
30=2 3 5
对于一个合数x被拆解为x=a*b
a一定是x的最小质数
24=2*12
45=3*15
线性筛
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
bool is[N];//is[i]=true表示i为合数
void init(int n){
is[1]=1;
vector<int>vec;//存放质数
for(int i=2;i<=n;i++){
if(is[i]==0)vec.push_back(i);
for(int j=0;j<vec.size();j++){
if(vec[j]*i>n)break;//跳过
is[vec[j]*i]=true;//标记
if(i%vec[j]==0)break;//跳过
}
}
}
全部评论 4
//埃氏筛，线性筛
//判断质数/寻找质数
//质数/素数 对于一个整数x，除了1和本身以外不能够被其他任何>1的整数整除的数字//O(x)
int a[N];//默认全部都是0/false
//埃氏筛 Nloglog
//线性筛，每个数字只标记一次
void prime(int n){
a[0]=a[1]=true;//true表示为非质数
for(int i=2;i<=n;i++){
if(a[i]==true)continue;
for(int j=2;ji<=n;j++){
a[ij]=true;
}
}
}
//暴力O(sqrt(x))
bool is_prime(ll x){//判断x是否是质数
if(x<=1)return false;
for(int i=2;i<=sqrt(x);i++){
for(int i=2;ii<=x;i++){//更推荐
for(int i=2,len=sqrt(x);i<=len;i++){
if(x%i==0)return false;
}
return true;
}
a[N];
for(int i=1;i<=n;i++){//nsqrt(n)//1e9
a[i]=is_prime(i);
}//质数 合数
// 对于任何一个合数，至少被拆解为几个质数乘积的形式
//至少两个
8=222
24=2223
//假设一个合数x被拆解为ab的形式
//问min(a,b)的最大可能是多少
24=124/212/38/46
x=a*a;
a^2=x;
a=sqrt(x);24=1 2 3 4 6 8 12 24//具有对称性
9=1 3 9
//x
for(int i=1;i<=x;i++){
if(x%i0)cout<<i<<' ';
}
for(int i=1;i<=sqrt(x);i++){
if(x%i0)cout<<i<<' ';
if(x/i!=i)cout<<x/i<<' ';
}
//给定一个数字x，判断x因数个数的奇偶性
//只有当x为完全平方数的时候，x的因子个数为奇数个埃氏筛:Nloglog
//2^10=1024
//log(2,1024)=10;
缺点
1.必须从小开始往大推
2.对于合数会被重复标记线性筛:O(n)
核心思想，找合数
24=2 3
30=2 3 5
对于一个合数x被拆解为x=ab
a一定是x的最小质数
24=212
45=3*15
线性筛
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
bool is[N];//is[i]=true表示i为合数
void init(int n){
is[1]=1;
vector<int>vec;//存放质数
for(int i=2;i<=n;i++){
if(is[i]==0)vec.push_back(i);
for(int j=0;j<vec.size();j++){
if(vec[j]*i>n)break;//跳过
is[vec[j]*i]=true;//标记
if(i%vec[j]==0)break;//跳过
}
}
}15小时前 来自 广东
0
有帮助，赞一个