中级光能
谁能帮我复习一下埃X筛法
都忘记了……
初级天翼
//埃氏筛法：快速求出一个区间的质数（1~n）
//埃氏筛法只能从头（2）开始筛，不能从中间开始筛！！！
/*
对于1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Step 1:0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 （叉掉除2外2的倍数和1）
Step 2:0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 （叉掉除3外3的倍数）
Step 3:0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 （叉掉除5外5的倍数）
叉5的倍数时，没有叉掉任何数，因此筛选结束，剩下的数全是质数。
*/
#include <iostream>
using namespace std;
const int MAXN=1000001;
bool mark[MAXN];//mark[]数组（下标从1开始）用来记录每个数是否是质数。
int main(){
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++)
mark[i]=true;
mark[1]=false;
for(int i=2;i<=n;i++)
if(mark[i]){
cnt++;
for(int j=2*i;j<=n;j+=i)
mark[j]=false;
}
cout<<cnt;
return 0;
}
在埃氏筛法中，一个合数被筛过的次数等于该合数的不同质因数的个数。
这是思路和普通的埃氏筛，优化的如下：
for(int i=2;i<=sqrt(n);i++)
if(mark[i]==true)
for(long long j=i*i;j<=n;j+=i)
mark[j]=false;
//注意：“在埃氏筛法中，一个合数被筛过的次数等于该合数的不同质因数的个数。”不成立！！！
埃氏筛速度很快！比普通方法快了不知道多少倍！！！
埃氏筛速度很快！比普通方法快了不知道多少倍！！！
埃氏筛速度很快！比普通方法快了不知道多少倍！！！
请勿举报！这个代码可以发！
请勿举报！这个代码可以发！
请勿举报！这个代码可以发！
曹灿阳在2020-07-28 18:32:11追加了内容
对于1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Step 1:0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 （叉掉除2外2的倍数和1）
Step 2:0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 （叉掉除3外3的倍数）
Step 3:0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 （叉掉除5外5的倍数）
叉5的倍数时，没有叉掉任何数，因此筛选结束，剩下的数全是质数。
曹灿阳在2020-07-29 17:15:05追加了内容
你这题目………………
中级天翼
z这题目……
资深天翼
埃氏筛法课后讲义（v2）
埃氏筛法
一、 埃氏筛法
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数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~10000范围内所有的质数。
#include<iostream> #define MAXN 10005 using namespace std; int a[MAXN]; int main() { int n; cin>>n; a[1]=1; for(int i=2;i<=MAXN;i++){ if(a[i]==0){ for(int j=2*i;j<=MAXN;j+=i) a[j]=1; } } for(int i=1;i<=MAXN;i++){ if(a[i]==0) cout<<i<<" "; } return 0; }
五、 埃氏筛法的好处
（1）运用筛法找出一个区间内的质数，非常高效。
（2）运用筛法的思想，可以将程序代码简化。
高级守护
埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
