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

**

质数筛(素数筛)

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

输入格式
无

输出格式
无

输入输出样例

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

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

#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之间的素数的倍数做标记（合数），然后判断即可。

#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乘之前所有已记录的质数

#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;
}

大概就是这样。
快马加鞭君为先，自古英雄出少年。

最后

以上就是土豪牛排为你收集整理的质数筛（根号、埃氏筛、欧拉筛）的全部内容，希望文章能够帮你解决质数筛（根号、埃氏筛、欧拉筛）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。