基本介紹
- 中文名：埃拉托斯特尼篩法
- 外文名：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 <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <vector>#include <algorithm>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) //列印}