基本介紹
- 中文名:埃拉托斯特尼篩法
- 外文名: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為0long 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實現
# python 原生實現def primes(n): P = [] f = [] for i in range(n+1): if i > 2 and i%2 == 0: f.append(1) else: f.append(0) i = 3 while i*i <= n: if f[i] == 0: j = i*i while j <= n: f[j] = 1 j += i+i i += 2 P.append(2) for x in range(3,n+1,2): if f[x] == 0: P.append(x) return Pn = 100 #100以內的素數P = primes(n)print P# Ipython 2.7實現import numpy as npa = np.arange(1,101)n_max = int(np.sqrt(len(a)))is_prime = np.ones(len(a),dtype=bool)is_prime[0] = Falsefor i in range(2,n_max) : if i in a[is_prime]: is_prime[(i**2-1)::i] = False print a[is_prime]
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) //列印}