质数筛（根号、埃氏筛、欧拉筛）

109 阅读 0 评论 72 点赞

我是靠谱客的博主土豪牛排，这篇文章主要介绍质数筛（根号、埃氏筛、欧拉筛），现在分享给大家，希望可以做个参考。

质数筛(素数筛)

**
【题目描述】
输入 n(n≤100) 个不大于 100000 的整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

输入格式
无

输出格式
无

输入输出样例

#输入：
5
3 4 5 6 7
#输出：
3 5 7

1.【遍历到根号法】
最暴力的解法，没啥好说的。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int n,t[101];
bool judge(int x)
{
for(int i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
return
0;
}
}
return 1;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>t[i];
if(t[i]<2)//去除异常数据（负数、0）和1
{
continue;
}
if(judge(t[i]))
{
cout<<t[i]<<' ';
}
}
return 0;
}

2.【埃氏筛】

大概思想就是把从二开始到100001之间的素数的倍数做标记（合数），然后判断即可。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int n,t[100001];
bool note[100001]={1,1};//标记为1的不是素数，0和1肯定不是素数
void AI()
{
for(int i=2;i<100001;i++)//从2开始做遍历
{
if(!note[i])
{
for(int j=2;j*i<100001;j++)
{
note[j*i]=1;
}
}
}
}
int main()
{
cin>>n;
AI();
for(int i=0;i<n;i++)
{
cin>>t[i];
if(!note[t[i]])//如果对应note的值为0则为素数，输出。
{
cout<<t[i]<<' ';
}
}
return 0;
}

3.欧拉筛
在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到 不重复 的目的。
简单点的理解就是用当前的i乘之前所有已记录的质数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int n,t[100001];
bool note[100001]={1,1};//标记为1的不是素数，0和1肯定不是素数
int primenumber[100001],k;//用来记录已有的质数（按顺序）
void Euler()
{
for(int i=2;i<100001;i++)
{
if(!note[i])
{
primenumber[k++]=i;//如果是素数的话就计入数组中
}
for(int j=0;primenumber[j]*i<100001&&j<k;j++)//用当前的值i乘已有的质数
{
note[i*primenumber[j]]=1;//标记为合数
if(i%primenumber[j]==0)//防止乘的primenumber不是最小质因子
{
break;
}
}
}
}
int main()
{
cin>>n;
Euler();
for(int i=0;i<n;i++)
{
cin>>t[i];
if(!note[t[i]])
{
cout<<t[i]<<' ';
}
}
return 0;
}