Liczby pierwsze – sito liniowe


Tematy pokrewne
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy

 

Problem

W przedziale <2,n> znaleźć wszystkie liczby pierwsze (ang. primes).

 

 

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 SSS \ { 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 lub
 p = p i q < q lub
 p = p i q = q i 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 × 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 = 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.

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 × 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 wykonuj K08...K09 ; w pętli wyrzucamy ze zbioru liczby złożone
K08:             usuń(S,x)  
K09:             xp × 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  

 

Program

Ważne:

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.

 

Lazarus
// Sito Liniowe
// Data   : 17.03.2008
// (C)2012 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.
Code::Blocks
// Sito Liniowe
// Data   : 17.03.2008
// (C)2012 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;
}
Free Basic
' Sito Liniowe
' Data   : 17.03.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

n =


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.