Algorytmy i Struktury Danych

W roku 1978 dwaj informatycy, David Gries z Cornell University oraz Jayadev Misra z University of Texas w Austin, opublikowali w ramach ACMs algorytm wyszukiwania liczb pierwszych, który działa w czasie liniowym \(O(n)\) i z tego powodu został nazwany sitem liniowym (ang. linear sieve). W porównaniu do algorytmu sita Eratostenesa, sito liniowe wyrzuca ze zbioru liczby złożone tylko jeden raz – sito Eratostenesa robi to wielokrotnie, gdy wyrzucana liczba rozkłada się na różne czynniki pierwsze. Z drugiej strony algorytm sita liniowego wykorzystuje intensywnie mnożenie, co może powodować spadek jego efektywności dla małych \(n\).

Algorytm operuje na zbiorze liczbowym \({S = \{2, 3, …, n\}}\), w którym zdefiniowano dwie operacje:

usuń(S, i) : jest zdefiniowana dla liczby \({i \in S; S \leftarrow S \setminus \{i\}}\)
następne(S, i) : jest funkcją zdefiniowaną dla liczby \({i \in S}\), której wynikiem jest bezpośrednio następna liczba naturalna w \(S\), większa od \(i\).

W algorytmie wykorzystuje się twierdzenie:

Liczba złożona \(x\) może zostać jednoznacznie zapisana jako:

x = p^k×q

gdzie:

\(p\) jest najmniejszą liczbą pierwszą dzielącą \(x\) bez reszty;
\(k \ge 1\);
\(p = q\) lub \(p\) jest mniejsze od najmniejszej liczby pierwszej, która dzieli \(q\) bez reszty.

Ponieważ w powyższy sposób nie można zapisać żadnej liczby pierwszej, zatem w celu usunięcia ze zbioru \(S\) liczb złożonych, algorytm musi jedynie wygenerować wszystkie kombinacje trójek \({(p, q, k)}\) i usunąć odpowiadające im liczby złożone \(x\). Sztuka polega na uzyskaniu każdej kombinacji dokładnie jeden raz oraz w takiej kolejności, aby następna kombinacja mogła być efektywnie wyliczona z kombinacji bieżącej. W tym celu algorytm stosuje mocne uporządkowanie \(\alpha\) dla liczb złożonych wyznaczanych przez trójki \({(p, q, k)}\), indukowane uporządkowaniem leksykograficznym odpowiednich trójek \({(p, q, k)}\).

Porządek \(\alpha\) zdefiniowany jest następująco:

x = p^k×q x = p^k×q
x α x <=>	p < p p = p ∧ q < q p = p ∧ q = q ∧ k < k

Poniższa tabelka przedstawia to uporządkowanie, jednocześnie wyjaśniając sposób pracy algorytmu. Wiersze zawierają kolejne wartości par \({(p, q)}\) wraz z zawartością zbioru \(S\) przed usunięciem liczb złożonych zawierających te składniki \(p\) i \(q\). Wartości liczb złożonych \({x = pk \cdot q}\) dla \({k = 1, 2, 3, 4}\) zostały zaznaczone na czerwono.

p	q	S
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 26 27 28 29 30 31 32
2	3	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
2	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
2	7	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
2	9	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
2	11	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
2	13	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
2	15	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
3	3	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
3	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
3	7	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
5	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
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

Zasada działania algorytmu sita liniowego jest następująca: Za \(p\) i \(q\) przyjmujemy pierwszą liczbę zbioru. Za \(k\) przyjmujemy 1. Następnie w pętli generujemy liczby \({x = pk \cdot q}\) dla kolejnych \({k = 1, 2, \dots}\) do momentu, gdy \(x\) przekroczy \(n\). Wygenerowane liczby \(x\) usuwamy ze zbioru. Wtedy za \(q\) przyjmujemy następną liczbę w zbiorze i całość powtarzamy. Jeśli pierwsze \(x\), dla \({k = 1}\) wykracza poza \(n\), to zmieniamy \(p\) i \(q\) na następną liczbę, która ze zbioru \(S\) nie została jeszcze wyrzucona. Algorytm kończymy, jeśli iloczyn \({p \cdot q}\) wykracza poza \(n\). Z przedstawionej tablicy wynika jasno, iż każde \(x\) pojawia się tylko jeden raz, nie dochodzi więc do zbędnych przebiegów.

Algorytm sita liniowego

Wejście:

\(n\) : liczba określająca górny kraniec przedziału poszukiwania liczb pierwszych; \({n \in \mathbb{N}, n > 1}\).

Wyjście:

Kolejne liczby pierwsze w przedziale od 2 do \(n\).

Elementy pomocnicze:

\(S\) : zbiór liczbowy; \({S \in \{2, 3, \dots , n\}}\).
\(p\) : mnożnik – liczba pierwsza; \({p \in S}\).
\(q\) : mnożnik drugi; \({q \in S}\).
\(x\) : liczba złożona; \({x \in S}\).
\(i\) : liczba; \({i \in S}\).

Lista kroków:

K01: S ← {2, 3, …, n} ; początkowo zbiór S zawiera
                      ; wszystkie liczby z przedziału
                      ; <2; n>
K02: p ← 2            ; pierwszy mnożnik
K03: Dopóki p×p ≤ n:
     wykonuj kroki K04…K11
K04:   q ← p          ; drugi mnożnik
K05:   Dopóki p×q ≤ n:
       wykonuj kroki K06…K10
K06:     x ← p×q      ; obliczamy liczbę złożoną
K07:     Dopóki x ≤ n: ; w pętli wyrzucamy ze zbioru
         wykonuj kroki K08…K09 ; liczby złożone
K08:       usuń(S, x)
K09:       x ← p×x    ; następna liczba złożona
K10:     q ← następne(S, q) ; za q przyjmujemy następną
                            ; liczbę w zbiorze, która nie
                            ; została jeszcze wyrzucona
K11:   p ← następne(S, p)   ; za p przyjmujemy następną
                            ; liczbę pierwszą ze zbioru
K12: Dla i = 2, 3, …, n:    ; przeglądamy zbiór i wypisujemy
     wykonuj krok K13       ; pozostałe w nim liczby pierwsze
K13:   Jeśli i ∈ S, 
       to pisz i
K14: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program w pierwszym wierszu czyta liczbę \(n\) i w następnych wierszach wypisuje kolejne liczby pierwsze zawarte w przedziale od 2 do \(n\).

Pascal

// Sito Liniowe
// Data: 17.03.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

type
  Tbarray = array of boolean;

var i, n, p, q, x : longword;
    S : Tbarray;

begin
  readln(n);
  setlength(S, n+1);
  for i := 2 to n do
    S[i] := true;
  p := 2;
  while p*p <= n do
  begin
    q := p;
    while p*q <= n do
    begin
      x := p*q;
      while x <= n do
      begin
        S[x] := false;
        x := p*x;
      end;
      repeat
        inc(q);
      until S[q];
    end;
    repeat
      inc(p);
    until S[p];
  end;
  for i := 2 to n do
    if S[i] then
      write(i, ' ');
  writeln;
end.

C++

// Sito Liniowe
// Data: 17.03.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int i, n, p, q, x;
  bool * S;

  cin >> n;
  S = new bool[n+1];
  for(i = 2; i <= n; i++)
    S[i] = true;
  p = 2;
  while(p*p <= n)
  {
    q = p;
    while(p*q <= n)
    {
      x = p*q;
      while(x <= n)
      {
        S[x] = false;
        x *= p;
      }
      while(!S[++q]);
    }
    while(!S[++p]);
  }
  for(i = 2; i <= n; i++)
    if(S[i])
      cout << i << " ";
  cout << endl;
  delete [] S;
  return 0;
}

Basic

' Sito Liniowe
' Data: 17.03.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As Uinteger i, n, p, q, x

Input n

Dim As Byte S(n+1)

For i = 2 To n
  S(i) = 1
Next
p = 2
While p*p <= n
  q = p
  While p*q <= n
    x = p*q
    While x <= n
      S(x) = 0
      x *= p
    Wend
    Do
      q += 1
    Loop Until S(q) = 1
  Wend
  Do
    p += 1
  Loop Until S(p) = 1
Wend
For i = 2 To n
  If S(i) = 1 Then _
    Print i;" ";
Next
Print
End

Python (dodatek)

# Sito Liniowe
# Data: 11.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

n = int(input())
s = [True]*(n+1)
p = 2
while p*p <= n:
    q = p
    while p*q <= n:
        x = p*q
        while x <= n:
            s[x] = False
            x *= p
        while 1:
            q += 1
            if s[q]: break
    while 1:
        p += 1
        if s[p]: break
for i in range(2, n+1):
    if s[i]:
        print(i, end=" ")
print()

Wynik:

100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

JavaScript

<html>
  <head>
    <title>
      Sito liniowe
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Sito Liniowe</b><br/>
          &nbsp;&nbsp;&nbsp;
          (C)2026
          mgr Jerzy Wałaszek
          &nbsp;&nbsp;&nbsp;
          <hr>
          n = <input
              type="text"
              name="inp_n"
              size="16"
              value="100"
              style="text-align:
                     right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Sito Liniowe
// Data   : 17.03.2008
// (C)2008 mgr Jerzy Wałaszek
//----------------------------

function main()
{
  var c,i,n,p,q,x,t,S;

  n = parseInt(document.frm
      .inp_n.value);
  c = 0;
  if(!isNaN(n))
  {
    t = "";
    S = new Array (n+1);
    for(i = 2; i <= n; i++)
      S[i] = true;
    p = 2;
    while(p * p <= n)
    {
      q = p;
      while(p * q <= n)
      {
        x = p * q;
        while(x <= n)
        {
          S[x] = false;
          x *= p;
        }
        while(!S[++q]);
      }
      while(!S[++p]);
    }
    for(i = 2; i <= n; i++)
      if(S[i])
      {
        t += i + " ";
        c++;
        if(c == 10)
        {
          c = 0;
          t += "<br/>";
        }
      }
  }
  else
    t = "Złe dane wejściowe!";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Liczby pierwsze – sito liniowe