Sito Eratostenesa

Sito Eratostenesa 

- przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału .

Ze zbioru liczb naturalnych z przedziału [2,n]\;, tj. \{2,3,4,\dots ,n\}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4,6,8,\dots .

                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

51           52           53           54           55           56           57           58           59           60

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6,9,12,\dots , przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

                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

51           52           53           54           55           56           57           58           59           60

Według tej samej procedury postępujemy dla liczby 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           33           34           35           36           37           38           39           40

41           42           43           -44-        45           46           47           48           49           50

51           52           53           54           55           56           57           58           59           60

Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

                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

51           52           53           54           55           56           57           58           59           60

Wykreślanie powtarzamy do momentu, gdy liczba i\;, której wielokrotność wykreślamy, będzie większa niż {\sqrt  {n}}.

Dla danej liczby n\; wszystkie niewykreślone liczby mniejsze, bądź równe n\; są liczbami pierwszymi.

                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

51           52           53           54           55           56           57           58           59           60

 

#include <iostream>
using namespace std;
 
const int n = 100;
bool numbersTable[n + 1]={0}; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);
 
int main()
{
    for (int i = 2; i*i <= n; ++i ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
    {
        if (numbersTable[i] == true) // jeżeli dana liczba jest już wykreślona
            continue; // to przejdź do kolejnej
        for (int j = 2*i ; j <= n; j += i) // przejdź od liczby 2 * i do n przesuwając się o i
            numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
    }
 
    cout << "Liczby pierwsze z przedziału od 2 do " << n << ":" << endl;
 
    for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
        if (numbersTable[i] == false) // jeśli liczba nie została usunięta ze zbioru
            cout << i << endl; // to ją wypisz
    return 0;
}