Sito Eratostenesa

Zbiór liczb naturalnych bez liczby 1 składa się z dwóch rodzajów liczb:

1. Liczb złożonych, które są podzielne przez liczby mniejsze z tego zbioru.

2. Liczb pierwszych, które nie są podzielne przez liczby mniejsze z tego zbioru.

Pierwszy rodzaj liczby to wielokrotności liczb mniejszych. Jeśli zatem ze zbioru usuniemy wielokrotności kolejnych liczb, to pozostaną w nim tylko liczby pierwsze. Na tej właśnie zasadzie działa sito Eratostenesa - przesiewa liczby wyrzucając ze zbioru ich kolejne wielokrotności.

Algorytm Sita Eratostenesa

Wejście:

    n  - określa górny kraniec przedziału <2,n>, w którym poszukujemy liczb pierwszych
Wyjście:

    Liczby pierwsze z przedziału <2,n>

Dane pomocnicze:

    T[ ] - tablica o elementach logicznych, których indeksy obejmują przedział <2,n>

    i  - kolejne liczby, których wielokrotności usuwamy
    w  - wielokrotności liczb i
 

Krok 1:	Ustaw wszystkie elementy T[ ] na true
Krok 2:	i  ← 2	; rozpoczynamy od liczby 2
Krok 3:	Jeśli i  ≥ n, to idź do kroku 11	; sprawdzamy, czy liczby osiągnęły koniec przedziału <2,n>
Krok 4:	w  ← i  + i	; liczymy pierwszą wielokrotność liczby i
Krok 5:	Jeśli w  > n, to idź do kroku 9	; sprawdzamy, czy wielokrotność wpada w przedział <2,n>
Krok 6:	T[w] ← false	; jeśli tak, to usuwamy ją ze zbioru liczb
Krok 7:	w  ← w  + i	; obliczamy następną wielokrotność
Krok 8:	Idź do kroku 5	; i kontynuujemy usuwanie wielokrotności
Krok 9:	i  ← i  + 1	; wyznaczamy następną liczbę
Krok 10:	Idź do kroku 3	; i kontynuujemy
Krok 11:	i  ← 2	; przeglądamy tablicę T[ ]
Krok 12:	Jeśli i  > n. to zakończ
Krok 13:	Jeśli T[i] = true, to pisz i	; wyprowadzamy liczby, które pozostały w T[ ]
Krok 14:	i  ← i  + 1
Krok 15:	Idź do kroku 12

 

#include <iostream>

using namespace std;

const unsigned N = 1000;  // definiuje koniec przedziału <2,N>

int main()
{
    bool T[N+1];  // tablica musi obejmować indeksy od 2 do N
    unsigned i,w;

    // ustawiamy wszystkie elementy T[] na true

    for(i = 2; i <= N; i++) T[i] = true;

    // eliminujemy w T[] wielokrotności

    for(i = 2; i < N; i++)
        for(w = i + i; w <= N; w += i) T[w] = false;

    // wyświetlamy indeksy elementów pozostawionych w T[]

    for(i = 2; i <= N; i++)
        if(T[i]) cout << i << " ";

    cout << endl << "--- KONIEC ---\n\n";

    return 0;
}