基本介紹
- 中文名：埃拉托斯特尼篩法
- 外文名：sieve of Eratosthenes
- 別名：篩法
- 提出者：埃拉托斯特尼
- 提出時間：250年
- 適用領域：數論
- 套用學科：數學
算式,步驟,Pascal實現,c++實現,Java實現,python實現,ES6實現,參見,
算式
要得到自然數n以內的全部素數，必須把不大於
的所有素數的倍數剔除，剩下的就是素數。
給出要篩數值的範圍n，找出以內的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重複下去......。
步驟
詳細列出算法如下：
- 列出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，序列變成：
- 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的倍數劃掉，主序列變成：
- 2 3 5 7 11 13 17 19 23 25
- 我們得到的素數有：2，3
- 25仍然大於3的平方，所以我們還要返回第二步：
- 序列中第一個素數是5，同樣將序列中5的倍數劃掉，主序列成了：
- 2 3 5 7 11 13 17 19 23
- 我們得到的素數有：2，3，5 。
- 因為23小於5的平方，跳出循環.
結論：2到25之間的素數是：2 3 5 7 11 13 17 19 23。
Pascal實現
var
f:array[1..100]of boolean; //存儲是否是質數
i,j,n:longint;
begin
readln(n);
fillchar(f,sizeof(f),true); //先假設都是質數
f[1]:=false; //注意：1不是質數
for i:=2 to trunc(sqrt(n)) do begin //最佳化：只需考慮根號n以內的數的倍數
if not f[i] then //最佳化：如果一個數不是質數，那么它的倍數一定已經被除去了
continue;
for j:=2 to n div i do //除去它的倍數
f[i*j]:=false;
end;
for i:=1 to n do //輸出
if f[i] then
write(i,' ');
writeln;
end.
c++實現
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 10000007 + 10;
const long long maxp = 700000;
int vis[maxn]; // i是合數vis為1，i是素數，vis為0
long long prime[maxp];
void sieve(long long n){
long long m = (long long)sqrt(n + 0.5);
memset(vis, 0, sizeof(vis));
vis[2] = 0;
for (long long i = 3; i <= m; i += 2) {
if(!vis[i])
for (long long j = i * i; j <= n; j += i)
vis[j] = 1;
if(i * i > n)
break;
}
}
long long gen(long long n){
sieve(n);
long long c = 1;
prime[0] = 2;
for (long long i = 3; i <= n; i += 2)
if(!vis[i])
prime[c++] = i;
return c;
}
int main()
{
long long n, c;
cout << "刷素數到n：";
cin >> n;
c = gen(n);
for (long long i = 0; i < c; i++)
printf("%lld", prime[i]);
cout << endl << c;
return 0;
}
Java實現
public class assf
{
public static void main(String[] args)
{
int aa[]=new int [101];
aa[2]=0;
int k=2,tt=0;
while(tt<101)
{
for(int i=1; i<aa.length; i++) //將不是素數的數篩出
{
if(i%k==0&&i!=k) aa[i]=1;
}
for(int i=1; i<aa.length; i++) //將篩選後的第一個數當做新的篩子
{
if(i>k&&aa[i]==0)
{
k=i;
break;
}
}
tt++;
}
for(int i=1; i<aa.length; i++)
if(aa[i]==0) System.out.printf("%d ",i);
}
}
python實現
# coding=UTF-8
def prinum(num=100, jud=True):
"""埃拉托斯特尼篩法 Sieve of Eratosthenes"""
try:
if num<2:
return False if jud else list()
elif num==2:
return True if jud else [2]
else:
num=num if isinstance(num, int) else int(num)+1
except:
raise ValueError("'num' must be a real number")
prili=[2]
prili.extend(list(range(3, num+1, 2)))
i=0
while prili[i]**2 < prili[-1]:
i+=1
for j in range(prili[i]**2, prili[-1]+1, prili[i]):
if j==num and jud:
return False
if j in prili:
prili.remove(j)
return (True if num in prili else False) if jud else prili
if __name__=="__main__":
"""
默認輸入的數字 num=100，默認jud=True
若 jud=True 則函式 prinum 功能為判斷輸入的數字是否為質數，這是默認項
若 jud=False 則函式 prinum 功能為以列表形式返回 2 到 num 的質數
"""
print(prinum(jud=False))
ES6實現
function* even(){//初始序列:3,5,7,9...
let n = 1
while(true){yield n+=2}
}
function* primes(max){
yield 2
var it = even(),n=null
while(true){
n = it.next().value
if(n>max){break}
yield n
it = (function*(it,n){
for(let x of it){
if(x%n>0){yield x} //篩選後續數值
}
})(it,n)
}
}
let Primes = primes(100) //100以內的質數
for(let x of Primes){
console.log(x) //列印
}
參見
- 三胞胎素數
- 素數判定法則
