埃拉托斯特尼篩法

埃拉托斯特尼篩法

埃拉托斯特尼篩法,簡稱埃氏篩或愛氏篩,是一種由希臘數學家埃拉托斯特尼所提出的一種簡單檢定素數的算法。要得到自然數n以內的全部素數,必須把不大於根號n的所有素數的倍數剔除,剩下的就是素數。

基本介紹

  • 中文名:埃拉托斯特尼篩法
  • 外文名:sieve of Eratosthenes
  • 別稱:篩法
  • 提出者:古希臘數學家埃拉托斯特尼所
  • 提出時間:公元前250
  • 套用學科:數學
  • 適用領域範圍:數論
算式,步驟,Pascal實現,c++實現,Java實現,python實現,ES6實現,參見,

算式

要得到自然數n以內的全部素數,必須把不大於
的所有素數的倍數剔除,剩下的就是素數。
給出要篩數值的範圍n,找出以內的素數。先用2去篩,即把2留下,把2的倍數剔除掉;再用下一個質數,也就是3篩,把3留下,把3的倍數剔除掉;接下去用下一個質數5篩,把5留下,把5的倍數剔除掉;不斷重複下去......。

步驟

詳細列出算法如下:
  1. 列出2以後的所有序列:
  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
  3. 標出序列中的第一個素數,也就是2,序列變成:
  4. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  5. 將剩下序列中,劃掉2的倍數,序列變成:
  6. 2 3 5 7 9 11 13 15 17 19 21 23 25
  7. 如果現在這個序列中最大數小於最後一個標出的素數的平方,那么剩下的序列中所有的數都是素數,否則回到第二步。
  8. 本例中,因為25大於2的平方,我們返回第二步:
  9. 剩下的序列中第一個素數是3,將主序列中3的倍數劃掉,主序列變成:
  10. 2 3 5 7 11 13 17 19 23 25
  11. 我們得到的素數有:2,3
  12. 25仍然大於3的平方,所以我們還要返回第二步:
  13. 現在序列中第一個素數是5,同樣將序列中5的倍數劃掉,主序列成了:
  14. 2 3 5 7 11 13 17 19 23
  15. 我們得到的素數有:2,3,5 。
  16. 因為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) //列印}

相關詞條

熱門詞條

聯絡我們