Liczby pierwsze – sito Eratostenesa


Tematy pokrewne   Podrozdziały
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
  Sito Eratostenesa
Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

 

Problem

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

 

 

Liczby pierwsze można wyszukiwać poprzez eliminację ze zbioru liczbowego wszystkich wielokrotności wcześniejszych liczb.

 

Przykład:

 

Mamy następujący zbiór liczb naturalnych:

 

{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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}

 

Ze zbioru wyrzucamy wszystkie wielokrotności pierwszej liczby 2. Otrzymujemy następujący zbiór:

 

{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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}

 

W zbiorze pozostały liczby nieparzyste – z wyjątkiem pierwszej liczby 2. Liczby podzielne przez dwa zostały wyeliminowane. Teraz eliminujemy wielokrotności kolejnej liczby 3. Otrzymamy następujący zbiór:

 

{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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}

 

Teraz w zbiorze pozostały liczby niepodzielne przez 2 i 3 – z wyjątkiem pierwszych 2 i 3. Zwróć uwagę, iż kolejna liczba 4 została już ze zbioru wyeliminowana. Skoro tak, to ze zbioru zniknęły również wszystkie wielokrotności liczby 4, ponieważ są one również wielokrotnościami liczby 2, a te wyeliminowaliśmy przecież na samym początku. Przechodzimy zatem do liczby 5 i eliminujemy jej wielokrotności otrzymując zbiór wynikowy:

 

{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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}

 

Oprócz 2,3 i 5 pozostałe w zbiorze liczby nie dzielą się już przez 2,3 i 5. Liczba 6 jest wyeliminowana (wielokrotność 2), zatem przechodzimy do 7. Po wyeliminowaniu wielokrotności liczby 7 zbiór przyjmuje postać:

 

{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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}

 

W zbiorze pozostały same liczby pierwsze.

 

{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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}

 

Przy eliminacji wystarczy usunąć ze zbioru wielokrotności liczb leżących w przedziale od 2 do pierwiastka z n. Wyjaśnienie tego faktu jest identyczne jak w algorytmie szukania liczb pierwszych przez testowanie podzielności. Jeśli liczba p jest złożona, to musi posiadać czynniki pierwsze w przedziale od 2 do pierwiastka z p.

 

Powyższe operacje wyrzucania wielokrotności prowadzą do przesiania zbioru wejściowego. W zbiorze pozostają tylko liczby pierwsze, liczby będące wielokrotnościami poprzedzających je liczb zostają ze zbioru odsiane. Algorytm dokonujący tej eliminacji nosi nazwę sita Eratostenesa (ang. Eratosthenes' sieve)  i jest jednym z najszybszych sposobów generowania liczb pierwszych.

 

Sito Eratostenesa

Sito Eratostenesa jest algorytmem dwuprzebiegowym. Najpierw dokonuje on eliminacji liczb złożonych ze zbioru zaznaczając je w określony sposób, a w drugim obiegu przegląda zbiór ponownie wyprowadzając na wyjście liczby, które nie zostały zaznaczone. Podstawowe znaczenie w tym algorytmie ma wybór odpowiedniej struktury danych do reprezentacji  zbioru liczb. Na tym polu można dokonywać różnych optymalizacji. W pierwszym podejściu zastosujemy tablicę wartości logicznych S. Element S[i] będzie odpowiadał liczbie o wartości i. Zawartość S[i] będzie z kolei informowała o tym, czy liczba i pozostała w zbiorze (S[i] = true) lub została usunięta (S[i] = false).

 

Rozwiązanie 1

Najpierw przygotowujemy tablicę reprezentującą zbiór liczbowy wypełniając ją wartościami logicznymi true. Odpowiada to umieszczeniu w zbiorze wszystkich liczb wchodzących w zakres od 2 do n. Następnie z tablicy będziemy usuwali kolejne wielokrotności początkowych liczb od 2 do pierwiastka całkowitego z n w pisując do odpowiednich elementów wartość logiczną false. Na koniec przeglądniemy zbiór i wypiszemy indeksy elementów zawierających wartość logiczną true – odpowiadają one liczbom, które w zbiorze pozostały.

Za pierwszą wielokrotność do wyrzucenia ze zbioru przyjmiemy kwadrat liczby i. Przyjrzyj się naszemu przykładowi. Gdy wyrzucamy wielokrotności liczby 2, to pierwszą z nich jest 4 = 22. Następnie dla wielokrotności liczby 3 pierwszą do wyrzucenia jest 9 = 32, gdyż 6 zostało wyrzucone wcześniej jako wielokrotność 2. Dla 5 będzie to 25 = 52, gdyż 10 i 20 to wielokrotności 2, a 15 jest wielokrotnością 3, itd. Pozwoli to wyeliminować zbędne obiegi pętli usuwającej wielokrotności.

 

Algorytm sita Eratostenesa

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  –  tablica wartości logicznych. S[i] {false,true}, dla i = 2,3,...,n.
g   zawiera granicę wyznaczania wielokrotności. g N
i  – przebiega przez kolejne indeksy elementów S[i]. i N
w  – wielokrotności wyrzucane ze zbioru S, w N
Lista kroków:
K01: Dla i = 2,3,...,n wykonuj S[i] ← true ; zbiór początkowo zawiera wszystkie liczby
K02: g ← [n] ; obliczamy granicę eliminowania wielokrotności
K03: Dla i = 2,3,...,g wykonuj kroki K04...K08 ; w pętli wyrzucamy ze zbioru wielokrotności i
K04:     Jeśli S[i] = false, to następny obieg pętli K03 ; sprawdzamy, czy liczba i jest w zbiorze
K05:     wi2 ; jeśli tak, wyrzucamy jej wielokrotności
K06:     Dopóki wn wykonuj kroki K07...K08 ; ze zbioru
K07:         S[w] ← false  
K08:         ww + i ; następna wielokrotność
K09: Dla i = 2,3,...,n wykonuj krok K10 ; przeglądamy zbiór wynikowy
K10:     Jeśli S[i] = true, to pisz i ; wyprowadzając pozostałe w nim liczby
K11: 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 Eratostenesa
// Data   : 17.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

type
  Tbarray = array of boolean;

var i,n,w : longword;
    S   : Tbarray;

begin
  readln(n);
  setlength(S,n+1);
  for i := 2 to n do S[i] := true;
  for i := 2 to round(sqrt(n)) do
    if S[i] then
    begin
      w := i * i;
      while w <= n do
      begin
        S[w] := false; inc(w,i);
      end;
    end;
  for i := 2 to n do if S[i] then write(i,' ');
  writeln;
end.
Code::Blocks
// Sito Eratostenesa
// Data   : 17.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned int g,i,n,w;
  bool * S;

  cin >> n;
  S = new bool[n + 1];
  for(i = 2; i <= n; i++) S[i] = true;
  g = (unsigned int)sqrt(n);
  for(i = 2; i <= g; i++)
    if(S[i])
    {
     w = i * i;
      while(w <= n)
      {
        S[w] = false; w += i;
      }
    } 
  for(i = 2; i <= n; i++) if(S[i]) cout << i << " ";
  cout << endl;
  delete [] S;
  return 0;
}
Free Basic
' Sito Eratostenesa
' Data   : 17.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger g,i,n,w

Input n
  
Dim As Byte S(n + 1)

For i = 2 To n: S(i) = 1: Next
g = Cuint(Sqr(n))
For i = 2 To g
  If S(i) > 0 Then
    w = i * i
    While w <= n
      S(w) = 0: w += i
    Wend
  End If
Next
For i = 2 To n
  If S(i) > 0 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 Eratostenesa
(C)2012 mgr Jerzy Wałaszek

n =


...

 

Rozwiązanie 2

Jedyną parzystą liczbą pierwszą jest 2. Zatem wszystkie pozostałe liczby parzyste (4, 6, 8, ...) już nie mogą być pierwsze. Utwórzmy tablicę S, której elementy będą reprezentowały kolejne liczby nieparzyste, począwszy od 3. Poniżej przedstawiamy początkowe przypisania indeksów liczbom nieparzystym.

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Komórka o indeksie i oznacza liczbę o wartości 2i+1. Np. komórka 7 reprezentuje liczbę 2x7+1=15.

Liczba o wartości k jest reprezentowana przez komórkę (k-1)/2. Np. liczbę 45 reprezentuje komórka (45-1)/2=22.

 

Z poprzedniego algorytmu pamiętamy, że pierwszą wyrzucaną wielokrotnością jest zawsze kwadrat liczby podstawowej. Nasza tablica rozpoczyna się od liczby 3, zatem pierwszą wielokrotnością, którą usuniemy, będzie liczba 9 na pozycji 4:

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Zauważ, że kolejne wielokrotności liczby 3, które są reprezentowane w tablicy, znajdują się w niej w odstępach co 3:

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Oznaczmy przez p odstępy pomiędzy wielokrotnościami, a przez q pozycję kwadratu liczby, której wielokrotności usuwamy z tablicy. Na początku mamy:

 

p0 = 3
q0 = 4

 

Po usunięciu tych wielokrotności tablica S nie będzie zawierała dalszych liczb podzielnych przez 3. Przejdźmy do kolejnej liczby, czyli do 5. Kwadrat 5 znajduje się na pozycji 12:

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Kolejne wielokrotności 5 znajdują się w naszej tablicy w odstępach co 5 (niektóre z nich są usunięte, ponieważ są również wielokrotnościami liczby 3) :

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Zapiszmy:

 

p1 = p0 + 2 = 3 + 2 = 5
q1 = q0 + 8 = 4 + 8 = 12

 

Następna liczba to 7 i jej pierwsza wielokrotność 49 na pozycji 24. Kolejne wielokrotności są w odstępach co 7:

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Znów zapiszmy:

 

p2 = p1 + 2 = 5 + 2 = 7
q2 = q1 + 12 = 12 + 12 = 24

 

Następna liczba to 9 i jej pierwsza wielokrotność 81 na pozycji 40. Kolejne wielokrotności są w odstępach co 9:

 

indeks   1   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 33 34 35 36 37 38 39 40
liczba 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81

 

Znów zapiszmy:

 

p3 = p2 + 2 = 7 + 2 = 9
q3 = q2 + 16 = 24 + 16 = 40

 

Wyrzucanie wielokrotności liczby 9 możemy pominąć, ponieważ sama liczba 9 jest już wyrzucona z tablicy przez 3. Ostatnią rozważaną tu liczbą jest 11 o kwadracie równym 121. Liczba 121 znajduje się na pozycji (121-1)/2 = 60:

 

p4 = p3 + 2 = 9 + 2 = 11
q4 = q2 + 20 = 40 + 20 = 60

 

W tablicy ta pozycja już nie występuje (indeksy kończą się na wartości 40), zatem kończymy. W S pozostały jedynie liczby pierwsze. Na koniec wyprowadźmy wzory rekurencyjne dla kolejnych wartości p oraz q. W tym celu wystarczy zauważyć prostą zależność (dla dociekliwych - wynika ona z rozkładu kwadratów liczb nieparzystych na sumę różnic - patrz: całkowity pierwiastek kwadratowy):

 

Kolejne p powstaje z poprzedniego przez dodanie 2. Kolejne q powstaje z poprzedniego przez dodanie 2(p-1):

 

i pi 2(pi-1) qi
0 3   4
1 3+2 = 5 2x(5-1) = 8 4+8 = 12
2 5+2 = 7 2x(7-1) = 12 12+12 = 24
3 7+2 = 9 2x(9-1) = 16 24+16 = 40
4 9+2 = 11 2x(11-1) = 20 40+20 = 60

 

Zatem możemy zapisać wzór rekurencyjny:

 

p0 = 3, q0 = 4  – wartości startowe

Dla i > 0:

    pi = pi-1 + 2
    qi = qi-1 + 2(pi - 1)

 

Po tych rozważaniach przystępujemy do zapisu algorytmu.

 

Algorytm ulepszonego sita Eratostenesa

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  –  tablica wartości logicznych. S[i] {false,true}, dla i = 1,2,...,n/2 - 1.
i, k  – przebiega przez indeksy S[i]. i N
p, q  – odstęp wielokrotności oraz pierwsza wielokrotność, p,q N
m  – połowa z n, m N
Lista kroków:
K01: Jeśli n  jest nieparzyste, to n ←  n + 1 ; n sprowadzamy do parzystego
K02: mn shr 1 ; m to połowa z n
K03: Dla i = 1,2,...,m - 1 wykonaj S[i] ← true ; w S są początkowo wszystkie liczby nieparzyste
K04: i ← 1 ; indeks kolejnych liczb liczb pierwszych w S
K05: p ← 3;  q ← 4 ; odstęp 3, pierwsza wielokrotność 4 (9)
K06: Jeśli S[i] = false, to idź do K11 ; przeskakujemy liczby wyrzucone z S
K07: kq ; w k indeks pierwszej wielokrotności liczby 2i + 1
K08: Dopóki k < m wykonuj kroki K09...K10 ; wyrzucamy z S wielokrotności
K09:     S[k] ← false  
K10:     kk + p ; wyznaczamy pozycję kolejnej wielokrotności, przesuniętą o odstęp p
K11: ii + 1 ; indeks następnej liczby w S
K12: pp + 2 ; zwiększamy odstęp wielokrotności
K13: qq + (p shl 1) - 2 ; wyznaczamy pierwszą wielokrotność
K14: Jeśli q < m, to idź do K06  
K15: Pisz 2 ; pierwsza liczba pierwsza wyprowadzana bezwarunkowo
K16: Dla i = 1,2,...,m-1 wykonuj krok K17 ; przeglądamy S wypisując pozostałe w niej liczby pierwsze
K17:     Jeśli S[i] = true, to pisz 2i + 1  
K18: 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
// Program: 0014
// Sito Eratostenesa
// Data   : 17.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

type
  Tbarray = array of boolean;

var i,k,p,q,n,m : longword;
    S           : Tbarray;

begin
  readln(n);
  if n and 1 = 1 then inc(n);
  m  := n shr 1;
  setlength(S,m+1);
  for i := 1 to m - 1 do S[i] := true;
  i := 1; p := 3; q := 4;
  repeat
    if S[i] then
    begin
      k := q;
      while k < m do
      begin
        S[k] := false; inc(k,p);
      end;
    end;
    inc(i); inc(p,2);
    inc(q,(p shl 1) - 2);
  until q >= m;
  write(2,' ');
  for i := 1 to m - 1 do if S[i] then write((i  shl 1) + 1,' ');
  writeln;
end.
Code::Blocks
// Program: 0014
// Sito Eratostenesa
// Data   : 17.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int i,k,p,q,n,m;
  bool * S;

  cin >> n;
  if(n & 1) n++;
  m = n >> 1;
  S = new bool[m + 1];
  for(i = 1; i < m; i++) S[i] = true;
  i = 1; p = 3; q = 4;
  do
  {
    if(S[i])
    {
      k = q;
      while(k < m)
      {
        S[k] = false; k += p;
      }
    }
    i++; p += 2;
    q += (p << 1) - 2;
  } while(q < m);
  cout << 2 << " ";
  for(i = 1; i < m; i++) if(S[i]) cout << (i << 1)+1 << " ";
  cout << endl;
  delete [] S;
  return 0;
}
Free Basic
' Program: 0014
' Sito Eratostenesa
' Data   : 17.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger i,k,p,q,n,m

Input n
If n And 1 = 1 Then n += 1
m = n Shr 1

Dim As Byte S(m + 1)

For i = 1 To m - 1:
  S(i) = 1:
Next
i = 1: p = 3: q = 4
Do
  If S(i) = 1 Then
    k = q
    While k < m
      S(k) = 0: k += p
    Wend
  End If
  i += 1: p += 2:
  q += (p Shl 1) - 2
Loop Until q >= m
Print 2;" ";
For i = 1 To m - 1
  If S(i) = 1 Then
    Print (i  Shl 1) + 1;" ";
  End If
Next
Print
End

 

Rozwiązanie 3

Autorem prezentowanego algorytmu jest chiński informatyk Xuedong Luo. W rozwiązaniu 2 zbiór liczbowy ograniczyliśmy do liczb nieparzystych. Teraz pójdziemy dalej i wrzucimy z tego zbioru dodatkowo wszystkie liczby podzielne przez 3. W efekcie nasz zbiór S przybierze postać:

 

Wartość indeksu i: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... in ip ... m
S[i] odpowiada liczbie: 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 ... 3in+2 3ip+1   n

 

gdize: in – indeks nieparzysty, ip – indeks parzysty

 

Element S[i] odwzorowuje liczbę niepodzielną ani przez 2, ani przez 3. Wartość liczby określamy w zależności od tego, czy indeks i jest parzysty, czy nieparzysty:

 

S[in] → 3in + 2
S[ip] → 3ip + 1

 

Dodatkowe założenie obejmuje n, które powinno spełniać równanie:

 

n = 3m + 2, gdzie m jest liczbą nieparzystą

 

Algorytm wyrzuca ze zbioru S wszystkie wielokrotności początkowych liczb. Najpierw wyznaczana jest pozycja kwadratu liczby na podstawie poprzedniej pozycji. W dalszej kolejności algorytm wyznacza wszystkie pozycje wielokrotności liczby począwszy od jej kwadratu i pomijając wielokrotności podzielne przez 2 lub przez 3. Elementy zbioru S znajdujące się na tych pozycjach są zaznaczane jako wyrzucone.

Algorytm jest trochę trudny do zrozumienia, lecz działa znakomicie. Zaletą jest zmniejszone 3 krotnie zapotrzebowanie na pamięć w stosunku do podstawowego algorytmu Euklidesa. Przy określaniu n pamiętaj, iż musi spełniać zależność n = 3m + 2, gdzie m jest liczbą nieparzystą. W przeciwnym razie ostatnie liczby pierwsze mogą nie zostać wyliczone.

 

Algorytm ulepszonego sita Eratostenesa

Wejście
n     liczba określająca górny kraniec przedziału poszukiwania liczb pierwszych, n N, n > 4, n = 3m + 2, gdzie m jest liczbą nieparzystą.
Wyjście:

Kolejne liczby pierwsze w przedziale od 2 do n.

Zmienne pomocnicze
m  – ilość elementów w zbiorze S. m N, m = [(n-2) / 3]
S  –  tablica wartości logicznych. S[i]  {false,true}, dla i = 1,2,...,m.
c  – pozycja pierwszej wielokrotności, wskazuje kwadrat liczby, c N
q  – górna granica pozycji liczb, których wielokrotności są usuwane ze zbioru, q N
k,t,ij  – zmienne służą do wyznaczania pozycji następnych wielokrotności. k,t,ij N
i,j  – indeksy elementów S, i,j N
Lista kroków:
K01: m ← (n - 2) div 3 ; obliczamy liczbę elementów w S
K02: Dla i = 1,2,...,m wykonuj S[i] ← true ; w zbiorze S są początkowo wszystkie liczby
K03: c ← 0 ; c będzie wskazywało pozycję kwadratu kolejnej liczby w zbiorze
K04: k ← 1; t ← 2 ; zmienne pomocnicze
K05: q ← [√n/3] ; granica pozycji liczb, których wielokrotności eliminujemy
K06: Dla i = 1,2,...,q wykonuj kroki K07...K15 ; w pętli wyznaczamy pozycje liczb do usunięcia
K07:     k ← 3 - k  
K08:     cc + 4k × i ; pozycja kwadratu liczby o indeksie i
K09:     j c ; do wyrzucania liczb posłuży indeks j
K10:     ij2i × (3-k) + 1  
K11:     tt + 4k  
K12:     Dopóki jm wykonuj kroki K13...K15 ; pętla usuwająca liczby
K13:         S[j] ← false; ; usuwamy j-tą liczbę
K14:         j j + ij ;  obliczamy pozycję następnej do usunięcia liczby
K15:         ijt - ij  
K16: Pisz 2 3 ; dwie początkowe liczby pierwsze wyprowadzamy bezwarunkowo
K17: Dla i = 1,2,...,m wykonuj kroki K18...K19 ; przeglądamy zbiór S
K18:     Jeśli S[i] = false, to następny obieg pętli K17 ; pomijamy liczby usunięte
K19:     Jeśli i nieparzyste, to pisz 2i + 2
    inaczej pisz 2i + 1
; inaczej wyprowadzamy wartości liczb, które w zbiorze pozostały
K20: 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 = 3m + 2, gdzie m jest liczbą nieparzystą. Jeśli n nie spełnia warunku, to program odpowiednio dopasuje n i m, co może skutkować powiększeniem przedziału wyszukiwania liczb.

 

Lazarus
// Sito Eratostenesa
// Data   : 17.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

type
  Tbarray = array of boolean;

var
  c,k,t,q,m,n,i,j,ij : longword;
  S : Tbarray;

begin
  readln(n);
  m := n div 3;
  if (m and 1) = 0 then inc(m); 
  setlength(S,m+1);
  c := 0; k := 1; t := 2;
  q := round(sqrt(n)) div 3;
  for i := 1 to m do S[i] := true;
  for i := 1 to q do
  begin
    k  := 3 - k;
    inc(c,(k shl 2) * i);
    j  := c;
    ij := (i shl 1) * (3 - k) + 1;
    inc(t,k shl 2);
    while j <= m do
    begin
      S[j] := false;
      inc(j,ij);
      ij   := t - ij;
    end;
  end;
  write(2,' ',3,' ');
  for i := 1 to m do
    if S[i] then
    begin
      if (i and 1) = 1 then write(3 * i + 2)
      else                  write(3 * i + 1);
      write(' ');
    end;
  writeln;
end.
Code::Blocks
// Sito Eratostenesa
// Data   : 17.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned int c,k,t,q,m,n,i,j,ij;
  bool * S;

  cin >> n;
  m = n / 3;
  if(!(m & 1)) m++; 
  
  S = new bool[m + 1];
  
  c = 0; k = 1; t = 2;
  q = ((unsigned int)sqrt(n)) / 3;
  for(i = 1; i <= m; i++) S[i] = true;
  for(i = 1; i <= q; i++)
  {
    k  = 3 - k;
    c  += (k << 2) * i;
    j  = c;
    ij = (i << 1) * (3 - k) + 1;
    t  += k << 2;
    while(j <= m)
    {
      S[j] =  false;
      j    += ij;
      ij   =  t - ij;
    }
  }
  cout << 2 << " " << 3 << " ";
  for(i = 1; i <= m; i++)
    if(S[i])
    {
      if(i & 1) cout << 3 * i + 2;
      else      cout << 3 * i + 1;
      cout << " ";
    }
  cout << endl;
  delete [] S;
  return 0;
}
Free Basic
' Sito Eratostenesa
' Data   : 17.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger c,k,t,q,m,n,i,j,ij

Input n
m = n \ 3
If (m And 1) = 0 Then m += 1 
  
Dim As Byte S(m + 1)

c = 0: k = 1: t = 2
q = Cuint(Sqr(n)) \ 3
For i = 1 To m: S(i) = 1: Next
For i = 1 To q
  k  =  3 - k
  c  += (k Shl 2) * i
  j  =  c
  ij =  (i Shl 1) * (3 - k) + 1
  t  += k Shl 2
  While j <= m
    S(j) = 0
    j    += ij
    ij   = t - ij
  Wend
Next
Print 2;" ";3;" ";
For i = 1 To m
  If S(i) = 1 Then
    If (i And 1) = 1 Then
      Print 3 * i + 2;
    Else
      Print 3 * i + 1;
    End If
    Print " ";
  End If
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 101

 



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.