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.
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:
- Stwórz listę kolejnych liczb od 2 do n (gdzie n to górny limit).
- Znajdź pierwszą liczbę na liście (początkowo 2) i wykreśl wszystkie jej wielokrotności większe od tej liczby.
- Znajdź następną liczbę na liście, której nie wykreślono i powtórz krok 2.
- 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:
