Sito EratostenesaEratostenesEratostenesa jest algorytmem znajdującym w danym przedziale $\lt 2, n \gt$wszystkie liczby pierwsze. Liczby pierwsze znajdują zastosowanie w kryptografiikryptografiakryptografii, m.in. w szyfrze RSA. Z powodu trudności w rozkładzie dużych liczb na czynniki pierwsze, algorytm RSA jest bezpieczny, a co za tym idzie – często stosowany w szyfrowaniu, a także przy tworzeniu podpisów cyfrowychpodpis cyfrowypodpisów cyfrowych. Więcej na ten temat dowiesz się z e‑materiału Szyfr RSAPl0GrlFTpSzyfr RSA.

Ideą algorytmu sita Eratostenesa jest wykrycie i usunięcie (wykreślenie) z zadanego przedziału liczb złożonych, zaczynając od wielokrotności liczby 2. Liczby złożone są wielokrotnościami liczb pierwszych. Jeżeli ze zbioru liczb naturalnych wykreślimy liczby złożone, pozostaną wyłącznie liczby pierwsze.

Algorytm zapisany za pomocą pseudokodu

Napiszmy teraz algorytm sita Eratostenesa za pomocą pseudokodu.

Zaczynamy od zadeklarowania zmiennej  n oraz n-elementowej tablicy. Przyjmujemy, że indeksy tablicy odpowiadają kolejnym liczbom naturalnym z analizowanego przedziału. Na początku zakładamy, że wszystkie liczby są pierwsze i dlatego każdemu z elementów przypiszemy wartość prawda. Wykreślanie będzie polegało na zmianie wartości wykreślanego elementu z wartości prawda na fałsz. Indeksy tablicy odpowiadające elementom o wartości prawda to poszukiwane liczby pierwsze.

n = wprowadź liczbę naturalną

T[n] = tablica wartości logicznych

dla s = 2, 3, ... n wykonuj:
	T[s] = prawda

Następnie tworzymy pętlę dla, w której będziemy sprawdzać czy element kryjący się w tablicy pod indeksem i ma wartość true. Jeżeli tak, wówczas w wewnętrznej pętli będziemy wykreślać wielokrotności indeksu tego elementu.

Iterator zewnętrznej pętli (i) będzie przyjmował wartości $\lt 2, \sqrt{n} \gt$. Deklarujemy zmienną j. Tak jak wspomnieliśmy, jej zadaniem będzie wskazanie indeksu wykreślanego elementu, czyli kolejnych wielokrotności liczby i. Inicjalizujemy ją kwadratem liczby i. Zostanie przez nas wykorzystana w wewnętrznej pętli dopóki. Wewnątrz pętli wyznaczamy kolejne wielokrotności liczby i, dodając jej wartość do zmiennej j. Wewnętrzną pętle przerywamy, kiedy wielokrotność i, zapisana w zmiennej j, będzie większa od ustalonego rozmiaru sita.

n = wprowadź liczbę naturalną

T[n] = tablica wartości logicznych

dla s = 2, 3, ... n wykonuj:
	T[s] = prawda
    
dla i = 2, 3, ...  <= pierwiastek(n) wykonuj:
	jeżeli T[i] == prawda wykonaj:
		j = i * i
        dopóki j <= n wykonuj:
        	T[j] = fałsz
            j = j + i

Ostatnim krokiem jest wypisanie liczb pierwszych.

Kompletny algorytm sita Eratostenesa zapisany za pomocą pseudokodu:

n = wprowadź liczbę naturalną

T[n] = tablica wartości logicznych

dla s = 2, 3, ... n wykonuj:
	T[s] = prawda
    
dla i = 2, 3, ...  <= pierwiastek(n) wykonuj:
	jeżeli T[i] == prawda wykonaj:
        j = i * i
        dopóki j <= n wykonuj:
        	T[j] = fałsz
            j = j + i
            
dla a = 2, 3, ... n wykonuj:
	jeżeli T[a] == prawda:
		wypisz a

n = wprowadź liczbę naturalną

T[n] = tablica wartości logicznych

dla s = 2, 3, ... n wykonuj:
	T[s] = prawda

i = 2

dopóki i * i <= n wykonuj:
    jeżeli T[i] == prawda wykonaj:
       j = i * i
       dopóki j <= n wykonuj:
          T[j] = fałsz
          j = j + i
    i = i + 1
            
dla a = 2, 3, ... n wykonuj:
    jeżeli T[a] == prawda:
        wypisz a

Schemat blokowy algorytmu

RTNLxs9u3KEXm

Ilustracja przedstawia schemat blokowy. 
 1 Zielony okrąg Start, 
 2 Fioletowy równoległobok Czytaj n,
 3 Błękitny prostokąt Ustaw wszystkie elementy tablicy T[] na prawda, 
 4 Błękitny prostokąt i=2, 
 5 Niebieski romb i mniejsze równe pierwiastek z n, 
 Dla nie w punkcie 5, 
   6 Błękitny prostokąt a=2, 
   7 Niebieski romb a mniejsze równe n, 
   Dla nie w punkcie 7, 
     8 Czerwony okrąg stop, 
   Dla tak w punkcie 7, 
     8 Niebieski romb T[a] = prawda,
     Dla tak w punkcie 8       9 Fioletowy równoległobok wypisz a, 
       10 Błękitny prostokąt a=a+1, 
       11 Powrót do kroku 7, 
     Dla nie w punkcie 8, 
       9 Błękitny prostokąt a=a+1,
       10 Powrót do kroku 7, 
 Dla tak w punkcie 5 
   6 Niebieski romb t[i]=prawda, 
   Dla nie w punkcie 6, 
     7 Błękitny prostokąt i=i+1, 
     8 Powrót do kroku 5, 
   Dla tak w punkcie 6 , 
     7 Błękitny prostokąt j=i razy i, 
     8 Niebieski romb  j mniejsze równe n, 
     Dla nie w punkcie 8, 
       9 Błękitny prostokąt i=i+1, 
       10 Powrót do kroku 5, 
     Dla tak w punkcie 8, 
       9 Błękitny prostokąt T[j]=fałsz, 
       10 Błękitny prostokąt j=j+i, 
       11 Powrót do kroku 8.

Słownik