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

©2020 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:

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:

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.

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

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

Wejście:

n  –   liczba określająca górny kraniec przedziału poszukiwania liczb pierwszych, nN, n  > 1.

Wyjście:

Kolejne liczby pierwsze w przedziale od 2 do n.

Zmienne 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  × 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,
        wykonuj kroki K08...K09
w pętli wyrzucamy ze zbioru 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ó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,
wykonuj krok K13
przeglądamy zbiór i wypisujemy 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
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
©2020 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.