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 ∈ S; S ← S \ {i}

następne(S, i) – jest funkcją zdefiniowaną dla liczby i ∈ 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 = pk × q

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 α dla liczb złożonych wyznaczanych przez trójki (p, q, k), indukowane uporządkowaniem leksykograficznym odpowiednich trójek (p, q, k).

Porządek α zdefiniowany jest następująco:

x = pk × q
x = pk × 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 = p^k × q dla k = 1, 2, 3, 4 zostały zaznaczone na czerwono.

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 = p^k × q dla kolejnych k = 1, 2, … 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 × 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

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 liczby złożone
         wykonuj kroki K08…K09
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óre 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

// 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.

// 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;
}

' 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

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

n = int(input())
S = [True, True]
for i in range(2, n + 1):
    S.append(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 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()

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