Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Liczby pierwsze – sito liniowe

SPIS TREŚCI

Problem

W przedziale liczb naturalnych <2, n> należy znaleźć wszystkie liczby pierwsze (ang. primes).

Rozwiązanie

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
gdzie:  p jest najmniejszą liczbą pierwszą dzielącą x bez reszty;
k ≥ 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 α 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 = pq < q
p = pq = qk < 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×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 468 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 46810 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 46810 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 46810 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 46810 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 46810 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 46810 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 468 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 468 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 468 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 468 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 468 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×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

Wejście:

n : liczba określająca górny kraniec przedziału poszukiwania liczb pierwszych; n ∈ N, n > 1.

Wyjście:

Kolejne liczby pierwsze w przedziale od 2 do n.

Elementy pomocnicze:

S : zbiór liczbowy; S ⊂ {2, 3, …, n}.
p : mnożnik – liczba pierwsza; p ∈ S.
q : mnożnik drugi; q ∈ S.
x : liczba złożona; x ∈ S.
i : liczba; i ∈ 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×pn:
     wykonuj kroki K04…K11
K04:   qp ; drugi mnożnik
K05:   Dopóki p×qn:
       wykonuj kroki K06…K10
K06:     xp×q ; obliczamy liczbę złożoną
K07:     Dopóki xn: ; w pętli wyrzucamy ze zbioru
         wykonuj kroki K08…K09 ; liczby złożone
K08:       usuń(S, x)
K09:       xp×x ; następna liczba złożona
K10:     qnastępne(S, q) ; za q przyjmujemy następną
                           ; liczbę w zbiorze, która nie
                           ; została jeszcze wyrzucona
K11:   pnastę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

Sito Liniowe
(C)2020 mgr Jerzy Wałaszek

n =



Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.