愛拉陶斯芬篩法

一、簡介

愛拉陶斯芬篩法，簡稱埃氏篩或愛氏篩，別名：愛拉托斯散篩法（或許是因為翻譯原因中文名字還有很多）

摺疊編輯本段二、步驟

我們詳細列出算法如下：

第一步，列出如下這樣以2開頭的序列：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第二步，標出序列中的第一個素數，主序列變成：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

第三步，將剩下序列中，第二項開始每隔一項劃掉(2的倍數,用紅色標出。），主序列變成：

2 3 5 7 9 11 13 15 17 19 21 23 25

第四步，如果現在這個序列中最大數小於第一個素數的平方，那么剩下的序列中所有的數都是素數，否則返回第二步。

本例中，因為25大於2的平方，我們返回第二步：

剩下的序列中第一個素數是3，將主序列中3的倍數劃出（紅色），主序列變成：

3 5 7 11 13 15 17 19 23 25

我們得到的素數有：2，3。

25仍然大於3的平方，所以我們還要返回第二步：

現在序列中第一個素數是5，同樣將序列中5的倍數劃出，主序列成了：

5 7 11 13 15 17 19 23 25

我們得到的素數有：2 3 5 。

因為25等於5的平方，跳出循環.

結論：去掉紅色的數字，2到25之間的素數是：2 3 5 7 11 13 17 19 23。

篩選的主要方法：

1.划去2的倍數；

2.划去3的倍數；

3 划去5的倍數；（4的倍數同為2的倍數，已被划去）

4.划去7的倍數；（6的倍數同為3的倍數，已被划去）

5.划去11的倍數；（8和10的倍數同為2的倍數，而9的倍數也是3的倍數）

所以驗證一個數是否是素數，可以用它來除以2，3，5，7，11......）

三、C++實現

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
39
40
41

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
usingnamespacestd;
constlonglongmaxn=10000007+10;
constlonglongmaxp=700000;
intvis[maxn];//i是合數vis為1，i是素數，vis為0
longlongprime[maxp];
voidsieve(longlongn){
longlongm=(longlong)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
vis=0;
for(longlongi=3;i<=m;i=i+2){
if(!vis)for(longlongj=i*i;j<=n;j+=i)vis[j]=1;
if(i*i>n)break;
}
}
longlonggen(longlongn){
ieve(n);
longlongc=1;
rime=2;
for(longlongi=3;i<=n;i=i+2)if(!vis)
rime[c++]=i;
returnc;
}
intmain()
{
freopen("in.in","r",stdin);
freopen("biao.out","w",stdout);
longlongn,c;
cout<<"刷素數到n：";
cin>>n;
c=gen(n);
for(longlongi=0;i<c;i++)
rintf("%lld",prime);
cout<<endl<<c;
return0;
}

愛拉陶斯芬篩法

基本介紹

一、簡介

摺疊編輯本段二、步驟

相關詞條

熱門詞條