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:

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

// 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]*(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()

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