Centrum wiedzy o technologiach i pracy w IT
sito eratostenesa python

Sito Eratostenesa w Pythonie pomaga odnaleźć liczby pierwsze

Ostatnia aktualizacja 14 marca, 2024

Sito Eratostenesa w języku Python to starożytny algorytm służący do znajdowania wszystkich liczb pierwszych mniejszych niż określona liczba. Jego nazwa pochodzi od greckiego matematyka Eratostenesa z Cyreny. Algorytm cechuje się efektywnością i prostotą w implementacji, co czyni go popularnym wyborem w wielu aplikacjach matematycznych i informatycznych.

Nie udało się zapisać Twojej subskrypcji. Spróbuj ponownie.
Udało się! Widzimy się niebawem – newsletter wysyłamy w każdy wtorek

Otrzymuj za darmo unikalne poradniki, dane i wiedzę o pracy w IT – dostarczane co tydzień

Klikając “Zapisz mnie” wyrażasz zgodę na otrzymywanie e-maili od redakcji, a także ofert partnerów oraz akceptujesz naszą Politykę prywatności.

Jak działa sito Eratostenesa

Zasada działania sita Eratostenesa jest dość prosta. Zacznijmy od wykreślenia liczb, które nie są pierwsze, w ten sposób:

  1. Stwórz listę kolejnych liczb od 2 do n (gdzie n to górny limit).
  2. Znajdź pierwszą liczbę na liście (początkowo 2) i wykreśl wszystkie jej wielokrotności większe od tej liczby.
  3. Znajdź następną liczbę na liście, której nie wykreślono i powtórz krok 2.
  4. Kontynuuj proces, aż nie będzie więcej liczb do sprawdzenia.

Liczby, które pozostały niewykreślone, są liczbami pierwszymi.

Implementacja w Pythonie

Poniżej przedstawiamy prostą implementację sita Eratostenesa w języku Python:

def sito_eratostenesa(n):
    """Zwraca wszystkie liczby pierwsze mniejsze lub równe n."""
    # Inicjalizacja listy, która oznacza wszystkie liczby jako potencjalnie pierwsze
    pierwsze = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        # Jeśli pierwsze[p] nie zostało zmienione, wtedy jest pierwsze
        if (pierwsze[p] == True):
            # Wykreślanie wszystkich wielokrotności p
            for i in range(p * p, n+1, p):
                pierwsze[i] = False
        p += 1
    # Zbieranie liczb pierwszych
    lista_pierwszych = []
    for p in range(2, n):
        if pierwsze[p]:
            lista_pierwszych.append(p)
    return lista_pierwszych

# Przykładowe użycie
print(sito_eratostenesa(30))

Optymalizacje

Choć sito Eratostenesa w języku Python jest stosunkowo prostym i skutecznym algorytmem, istnieje kilka optymalizacji, które mogą znacząco poprawić jego wydajność, zwłaszcza dla dużych liczb. Oto niektóre z nich:

  • Wykreślanie wielokrotności od p^2: Wielokrotności liczb mniejsze niż p^2 zostały już wykreślone przez mniejsze liczby pierwsze przed p, więc rozpoczynamy wykreślanie od p^2. To zmniejsza liczbę operacji, ponieważ nie musimy ponownie sprawdzać liczb wykreślonych przez wcześniejsze liczby pierwsze.
  • Używanie tylko nieparzystych liczb: Poza 2, żadna parzysta liczba nie może być liczbą pierwszą, więc algorytm można zoptymalizować, przechowując i sprawdzając tylko nieparzyste liczby. Pozwala to na redukcję przestrzeni poszukiwań o połowę, co jest znaczącym usprawnieniem, szczególnie dla dużych wartości n.
  • Sito segmentowe: Ta technika polega na podziale zakresu poszukiwań na mniejsze segmenty, które mieszczą się w pamięci cache. Dzięki temu, operacje na danych mogą być wykonywane szybciej, ponieważ ogranicza się potrzebę dostępu do wolniejszej pamięci głównej. Sito segmentowe jest szczególnie przydatne przy wyszukiwaniu liczb pierwszych w bardzo dużych zakresach.
  • Wykorzystanie bitsetów zamiast tablicy booli: Przechowywanie informacji o tym, czy liczba jest pierwsza, jako bit zamiast wartości boolowskiej (True/False) pozwala na znaczącą redukcję zużycia pamięci. Każdy bit reprezentuje stan dla pojedynczej liczby, dzięki czemu można przechowywać dane o wielu liczbach w mniejszej ilości pamięci.
  • Optymalizacja pętli: Modyfikując warunki w pętli, na przykład poprzez zastosowanie odpowiednich formuł do wyznaczania początku iteracji, możemy uniknąć niepotrzebnych sprawdzeń. Na przykład, rozpoczynając iterację od kwadratu bieżącej liczby pierwszej, pomijamy liczby wykreślone jako wielokrotności mniejszych liczb pierwszych.

Czytaj także:

Składnia Pythona. Przegląd podstawowych elementów

Funkcje rekurencyjne w Pythonie – podstawy

Total
0
Shares
_podobne artykuły