Sito Eratostenesa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Sito Eratostenesa
154 KB
Przykładowe działanie Sita Eratostenesa
Struktura danych Tablica, lista
Złożoność
Czasowa O((n log n)(log log n))
Pamięciowa O(n)

Sito Eratostenesa - przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału [2,n]\;.

Algorytm[edytuj]

Ze zbioru liczb naturalnych z przedziału [2,n]\;, tj. \{2, 3, 4, \dots, n\}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4, 6, 8, \dots.

  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 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6, 9, 12, \dots, przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

  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 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60

Według tej samej procedury postępujemy dla liczby 5.

  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 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60

Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

  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 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60

Wykreślanie powtarzamy do momentu, gdy liczba i\;, której wielokrotność wykreślamy, będzie większa niż \sqrt{n}.

Dla danej liczby n\; wszystkie niewykreślone liczby mniejsze, bądź równe n\; są liczbami pierwszymi.

  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 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60

Powyższy algorytm można zapisać w postaci następującego pseudokodu[1]:

Wejście: liczba całkowita n > 1
 
Niech A będzie tablicą typów logicznych indeksowaną liczbami całkowitymi od 2 do n
początkowo wypełniona wartościami true
 
 for i := 2, 3, 4, ..., nie więcej niż \sqrt{n}:
  if A[i] = true:
    for j :=  2i, 3i, 4i, ..., nie więcej niż n :
      A[j] := false
 
Wyjście: wartości i takie, że A[i] zawiera wartość true.

Przypisy

Zobacz też[edytuj]

Linki zewnętrzne[edytuj]