资深天翼
1、埃氏筛是什么？
2、埃氏筛怎么用？
3、埃氏筛适用于哪种类型的题？
有效期：到5月9日。
高级天翼
这是我们卢老师给我们上的，希望对你有帮助：
望采纳~~
新手天翼
埃式筛可以大幅度减少你程序运行的速度，比经典找质数的方法快许多倍，望采纳
王子逸在2020-05-07 21:34:17追加了内容
埃式筛运用于找质数哦
王子逸在2020-05-08 18:43:50追加了内容
希望对你有用
高级天翼
高级守护
中级天翼
那么 现在我让你判断1-20 之内的素数 你会怎么做
从1 遍历到20 挨个判断一下是不是素数 对吧
那么我们来分析一下复杂度 如果不理解什么是复杂度 你就认为我们算一下循环次数好了
从1-20 需要遍历20次 对于每个数 极端情况下 需要sqrt（n）次才完成能判断
这一共是多少次呢 sqrt(2)+sqrt(3)+sqrt(4)+sqrt(5)+.........sqrt(20) 次 对吗
通过计算器 计算得到 答案是60 也就是需要60次
那么我们再来看下 我们使用埃氏筛需要几次
首先 外面的循环 毋庸置疑 从2-20遍历 需要20次（其实是19 我们忽略 进为20）
我们来看里面的操作
从2开始 2是素数 那么4不是 6不是 8也不是 10、12、14、16、18、20 都不是 这是9次操作
然后3开始 6 9 12 15 18 都不是素数 这是5次操作
然后4 跳过 5 跳过 6 跳过
从7开始 14 不是素数 这是1次操作
后边的 8 9 10 11 12 14 15 16 18 20 都会跳过
而11 13 17 19 都不会操作 因为他们的倍数 大于20了
那么一共进行了20+9+5+1=35次操作 比那个60少了将近一半
其实因为我举的例子很小 只到20 所以你看到的才快了这么点
你可以想一下 如果数字变得很大的时候 比如一千万 你用普通的筛法 是需要更多次数的
所以 这个埃氏筛法快的其实不止这么一点--（至于究竟快多少 先不管了 你只要知道很快就好了）
下面说下 怎么用它
明白了 原理 用起来就很灵活了
比如
问题一 求1-20之间的素数个数
int main(){
int cnt=0;//用来计数
bool isprime[21];
for(int i=0;i<=20;i++)isprime[i]=true;//先全部置为真
isprime[0]=isprime[1]=false;//1 0 不是素数
for(int i=2;i<=20;i++){//从2开始往后筛
if(isprime[i]){
for(int j=2*i;j<=20;j+=i){
isprime[j]=false;
}
}
if(isprime[i]){
cnt++;//如果是素数 就计数
}
}
printf("%d",cnt);
}
问题二
就是ppt上的题目
#include<stdio.h>
#include<algorithm>
#include<math.h>
const int maxn=1e6+7;//总的范围规定在这里
using namespace std;
//我们将这个埃氏筛法写成一个函数
bool isprime[maxn];
void sieve(){
for(int i=0;i<=maxn;i++)isprime[i]=true;
isprime[0]=isprime[1]=false;
for(int i=2;i<=maxn;i++){//从2开始往后筛
if(isprime[i]){
for(int j=2*i;j<=maxn;j+=i){
isprime[j]=false;
}
}
}
}
int l,r;
int main(){
//我们在程序刚开始 先调用这个函数
//把这个isprime数组处理成我们想要的样子 用来判断素数
//这就是预处理的思想 我们在开头处理这一次
//把isprime数组 里面 下标是素数的全部变成了true
//后边想判断是不是素数 直接用isprime[i]是不是真就好了
sieve();
int cnt=0;//计数
scanf("%d%d",&l&r);//输入 l和r
for(int i=l;i<=r;i++){//遍历 l到r 判断就行了
if(isprime[i]){
cnt++;
}
}
printf("%d",cnt);
}
问题三 输入一个数n 判断他是不是素数（多组测试数据）
n的范围是 (n<1e6)
这个题很有意思 题上说有多组测试数据（没说几组） 每次给你一个n
那么其实意思就是说 有很多个n让你判断 他们是不是素数
而且n最大是1e6
那么你们想一下
如果我第一个数给你1000000 你用普通的判断素数的方法 需要sqrt（n）次才能判断出来
也就是3000次才能判断出来是不是素数 对吧
3000次也不多 那如果我输入一共一万组呢 就需要3000*10000次了吧
所以 这个时候 就体现了 预处理的重要性
我们先预处理出来 1e6以内的所有素数 这样不管你输入啥 我直接去看 是不是素数就好了
对吧
那么 预处理 有些同学也想到了 但是他用最普通的筛法去做预处理
那么你想一下 1e6每个你都需要去判断一下是不是素数 我刚才在上边算了 20以内的素数需要60次才能判断出来
那1e6以内 需要多少次呢 我告诉你 大概需要1e9次（也就是十亿次）
而用埃氏筛法需要几次呢 可能你们现在还不会算 我直接告诉你们 需要70万次
十亿 和 七十万 差别不用我说了吧 这就是这个算法的效率 也是算法的魅力所在。
#include<stdio.h>
#include<algorithm>
#include<math.h>
const int maxn=1e6+7;//总的范围规定在这里
using namespace std;
//我们将这个埃氏筛法写成一个函数
bool isprime[maxn];
void sieve(){
for(int i=0;i<=maxn;i++)isprime[i]=true;
isprime[0]=isprime[1]=false;
for(int i=2;i<=maxn;i++){//从2开始往后筛
if(isprime[i]){
for(int j=2*i;j<=maxn;j+=i){
isprime[j]=false;
}
}
}
}
int n;
int main(){
sieve();//预处理
//输入 n
while(scanf("%d",&n)!=EOF){
if(isprime[n]){
printf("Yes\n");
}
else{
printf("No\n");
}
}
}
初级天翼
就是找质数的算法
资深守护
我不知道你在说什么？？？
高级天翼
A1：埃氏筛是筛质数的方法。
A2：埃氏筛的思想是：
要找1-n的质数，定义一个数组记录当前这个数是否是质数，从2开始循环，
如果当前的数是质数就写第二层从i到n循环，所有i的倍数都用数组记录，筛掉。
所有的都筛掉之后剩下的就是质数。
for(int i=2;i<=n;i++)
if(!a[i]){
for(int j=2*i;j<=n;j+=i)//筛掉质数的倍数,标记,剩下的是质数
a[j]=1;
cnt++;
}
cout<<cnt<<endl;//cnt表示1-n质数的个数
//a数组是一个初值全部为0的bool桶数组PS：非具体题目代码，勿举报！！！
A3：埃氏筛适用于给出范围，找质数的题目。
中级天翼
初级天翼
埃氏筛就是一个几乎没人用的东西（划掉
思路就是如果某个数是质数，那么这个数的倍数不是质数
一般就写欧拉筛叭，线性的复杂度更快些
当然你可以随手就写个杜教筛、min 25筛（大雾
新手天翼
一、 埃氏筛法
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
二、 具体思想：
给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。
三、 算法流程
排出从1~N的数列：1 2 3 4 5 6 7 8 9 10 11 12 ……
1不是素数，也不是合数，划去
2是素数，把N以内所有2的倍数划去
3是素数…… 重复划去过程直到sqrt(N)
四、 埃氏筛法的好处
（1）我们发现运用筛法找出一个区间内的质数，非常高效。
（2）运用筛法的思想，可以将程序代码简化。
资深天翼
倒计时：两天
新手启示者
1
