Sito Eratostenesa - implementacja w Pythonie

Sito Eratostenesa to efektywny algorytm do znajdowania liczb pierwszych. Poniżej przedstawiamy jego implementację w języku Python wraz z objaśnieniami.

Podstawowa implementacja

Oto prosta implementacja Sita Eratostenesa w Pythonie:

def sieve_of_eratosthenes(n): # Tworzymy listę booli, początkowo wszystkie liczby są uważane za pierwsze is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1): if is_prime[i]: # Oznaczamy wielokrotności i jako złożone for j in range(i*i, n + 1, i): is_prime[j] = False # Zwracamy listę liczb pierwszych return [num for num in range(2, n + 1) if is_prime[num]]
# Przykład użycia
print(sieve_of_eratosthenes(30))

Wynik działania tego kodu to:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Objaśnienie kodu

  1. Tworzymy listę is_prime, gdzie początkowo wszystkie liczby (oprócz 0 i 1) są oznaczone jako pierwsze.
  2. Iterujemy przez liczby od 2 do pierwiastka z n (wystarczy sprawdzić do tej wartości).
  3. Jeśli liczba jest oznaczona jako pierwsza, oznaczamy wszystkie jej wielokrotności jako złożone.
  4. Na końcu zwracamy listę liczb, które pozostały oznaczone jako pierwsze.

Optymalizacja

Możemy zoptymalizować ten algorytm, zaczynając oznaczanie wielokrotności od kwadratu liczby pierwszej:

def optimized_sieve(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1): if is_prime[i]: is_prime[i*i::i] = [False] * len(is_prime[i*i::i]) return [num for num in range(2, n + 1) if is_prime[num]]
print(optimized_sieve(30))

Ta wersja jest bardziej efektywna, szczególnie dla większych liczb.

Analiza złożoności

Złożoność czasowa tego algorytmu to O(n log log n), co czyni go jednym z najszybszych algorytmów do znajdowania wszystkich liczb pierwszych w danym zakresie.

Zastosowania w Pythonie

Sito Eratostenesa w Pythonie może być używane do:

  • Generowania dużych list liczb pierwszych
  • Rozwiązywania problemów matematycznych związanych z liczbami pierwszymi
  • Jako część bardziej złożonych algorytmów w teorii liczb

Ćwiczenie

Spróbuj zmodyfikować powyższy kod, aby:

  1. Znaleźć wszystkie liczby pierwsze mniejsze niż 1000.
  2. Policzyć, ile jest liczb pierwszych w danym zakresie.
  3. Znaleźć największą liczbę pierwszą mniejszą od danej liczby.

Podsumowanie

Implementacja Sita Eratostenesa w Pythonie jest eleganckim przykładem, jak starożytny algorytm może być efektywnie zaimplementowany w nowoczesnym języku programowania. Zrozumienie i umiejętność implementacji tego algorytmu jest cenną umiejętnością dla każdego programisty i matematyka.