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

Słownik