INF.04Algorytmika i Struktury Danych
Sito Eratostenesa (Liczby pierwsze)
Wydajny algorytm wyznaczania wszystkich liczb pierwszych w przedziale od 2 do n poprzez cykliczne wykreślanie wielokrotności znalezionych liczb pierwszych.
Zasada działania:
- Tworzymy tablicę logiczną o rozmiarze n+1, początkowo wypełnioną wartościami
true. Indeksy 0 i 1 oznaczamy jakofalse. - Dla każdej liczby i od 2 do sqrt{n}:
- Jeśli i nie została wykreślona, wykreślamy wszystkie jej wielokrotności: 2i, 3i, 4i, ... ≤ n.
- Indeksy, które pozostały z wartością
true, są liczbami pierwszymi.
Złożoność czasowa:
O(n log(log n)) – znacznie szybsza niż sprawdzanie każdej liczby pojedynczo!
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Sito Eratostenesa (Liczby pierwsze) lub rozpocznij trening.