Sito Eratostenesa | Korepetycje do matury z informatyki - Maurycy Gast

Sito Eratostenesa

Sito Eratostenesa jest algorytmem, za którego autora uznawany jest Eratostenes z Cyreny. Jest to postać znana z wyznaczenia obwodu Ziemi, oraz oszacowania odległości Słońca i Księżyca do Ziemi.

Sito Eratostenesa służy do wyznaczania liczb pierwszych z zadanego przedziału, od 2 do n. Dla przypomnienia: liczba pierwsza to taka liczba, która ma dokładnie dwa dzielniki – 1 oraz siebie samą. Z tego powodu liczba 1 nie jest liczbą pierwszą, więc najmniejszą taką liczbą jest 2.

Co to jest sito Eratostenesa?

Działanie algorytmu opiera się na zasadzie, która wynika bezpośrednio z definicji liczby pierwszej. W pierwszym kroku tworzymy tablicę, w której wszystkie wartości ustawione są na wartość prawda. Każda z tych wartości będzie odpowiadała jednej liczbie z naszego przedziału. Wybieramy najmniejszą liczbę pierwszą z tego przedziału – jest nią 2. Następnie, dla wartości kolejno 2, 4, 6…, czyli wszystkich wielokrotności tej liczby większych od niej samej, komórki ustawiamy na fałsz. W następnym kroku należy wybrać kolejną liczbę z przedziału, dla której odpowiadająca komórka ma wartość prawda. Powtarzamy te kroki aż do momentu, w którym nie wykluczymy wielokrotności wszystkich liczb.

sito eratostenesa c++
Działanie algorytmu, jakim jest sito Eratostenesa, jest zasada wynikająca bezpośrednio z definicji liczb pierwszych.

Wartości, których komórki mają wartość prawda, to liczby pierwsze. Zauważmy, że górną granicą pętli, która przechodzi po liczbach, jakich wielokrotności sprawdzamy, jest pierwiastek z n. Pozwala to na znaczne przyśpieszenie działania programu.

Przeanalizujmy działanie tego algorytmu dla n=16. Początkowo nasza tabela prezentuje się tak:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Dla wszystkich podanych tutaj wartości, zawartość tablicy jest równa prawda. Teraz zaznaczmy na czerwono wszystkie wielokrotności liczby 2.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Teraz powtórzmy ten proces dla liczby 3.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Kolejnym krokiem byłoby zaznaczenie wielokrotności liczby 5, jednak byłaby ona większa, niż pierwiastek z n. Oznacza to, że wykonywanie naszego algorytmu zakończyło się. Liczby niezamalowane na czerwono są liczbami pierwszymi. Wynik naszego algorytmu to zatem:

2, 3, 5, 7, 11, 13

Złożoność pamięciowa tego algorytmu to O(n), czyli liniowa – w przypadku dużych liczb może ona okazać się problemem. Złożoność obliczeniowa to  O(n log log n). Choć jest to bardzo nietypowa złożoność, oznacza to, że nasz algorytm jest relatywnie szybki.

Sito Eratostenesa – Python:

n = int(input())
tablica = [True] * (n+1)
for i in range(2, n):
    if tablica[i]:
        for j in range(2*i, int(n**0.5) + 1, i):
            tablica[j] = False
for i in range(2,len(tablica)):
    if tablica[i]:
        print(i, end=",")

Sito Eratostenesa – C++:

#include <iostream>
using namespace std;
int main()
{
    int n = 0;
    cin >> n;
    n++;
    bool *tab = new bool[n];
    for(int i = 0; i < n; i++)
        tab[i] = true;
    for(int i = 2; i * i <= n; i++)
        if(tab[i])
            for(int j = 2 * i; j < n; j += i)
                tab[j] = false;
    for(int i = 2; i < n; i++)
        if(tab[i])
            cout << i <<",";
    return 0;
}

Wpisy, które mogą Cię zainteresować:



Dodaj komentarz

kurs maturalny informatyka