Algorytm sita Eratostenesa: Python, C++ Przykład
Sito Eratostenesa jest najprostszym sitem liczb pierwszych. Jest to algorytm liczb pierwszych, który przeszukuje wszystkie liczby pierwsze w danym przedziale. Istnieje kilka sit liczb pierwszych. Na przykład: Sito Eratostenesa, Sito Atkinsa, Sito Sundarama itd.
Słowo "sito” oznacza naczynie filtrujące substancje. Zatem algorytm sita w Python i innych językach odnosi się do algorytmu filtrującego liczby pierwsze.
Ten algorytm filtruje liczbę pierwszą w podejściu iteracyjnym. Proces filtrowania zaczyna się od najmniejszej liczby pierwszej. Liczba pierwsza to liczba naturalna większa od 1, która ma tylko dwa dzielniki, tj. 1 i samą liczbę. Liczby, które nie są liczbami pierwszymi, nazywane są liczbami złożonymi.
Na sicie metody Eratostenesa wybiera się najpierw małą liczbę pierwszą, a następnie odfiltrowuje się wszystkie jej wielokrotności. Proces przebiega w pętli w zadanym zakresie.
Na przykład:
Weźmy zakres liczb od 2 do 10.
Po zastosowaniu sita Eratostenesa otrzymamy listę liczb pierwszych 2, 3, 5, 7
Algorytm sita Eratostenesa
Oto algorytm sita Eratostenesa:
Krok 1) Utwórz listę liczb od 2 do podanego zakresu n. Zaczynamy od 2, ponieważ jest to najmniejsza i pierwsza liczba pierwsza.
Krok 2) Wybierz najmniejszą liczbę na liście, x (początkowo x jest równe 2), przejrzyj listę i przefiltruj odpowiadające jej liczby złożone, zaznaczając wszystkie wielokrotności wybranych liczb.
Krok 3) Następnie wybierz kolejną liczbę pierwszą lub najmniejszą niezaznaczoną liczbę na liście i powtórz krok 2.
Krok 4) Powtarzaj poprzedni krok, aż wartość x będzie mniejsza lub równa pierwiastkowi kwadratowemu z n (x<=).
Uwaga: Rozumowanie matematyczne jest dość proste. Zakres liczb n można rozłożyć na czynniki jako:
n=a*b
Ponownie, n =*
= (współczynnik mniejszy niż ) * (współczynnik większy niż
)
Zatem przynajmniej jeden z czynniki pierwsze lub oba muszą być <=. Zatem przejazd do
to wystarczy.
Krok 5) Po wykonaniu tych czterech kroków pozostałe nieoznakowane liczby będą wszystkimi liczbami pierwszymi w danym zakresie n.
Przykład:
Weźmy przykład i zobaczmy, jak to działa.
W tym przykładzie znajdziemy listę liczb pierwszych od 2 do 25. Zatem n=25.
Krok 1) W pierwszym kroku weźmiemy listę liczb od 2 do 25, ponieważ wybraliśmy n=25.
Krok 2) Następnie wybieramy najmniejszą liczbę z listy, x. Początkowo x=2, ponieważ jest to najmniejsza liczba pierwsza. Następnie przeglądamy listę i zaznaczamy wielokrotności 2.
Wielokrotności 2 dla danej wartości n to: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.
Uwaga: Kolor niebieski oznacza wybraną liczbę, a kolor różowy oznacza wyeliminowane wielokrotności
Krok 3) Następnie wybieramy kolejną najmniejszą nieoznaczoną liczbę, czyli 3, i powtarzamy ostatni krok, zaznaczając wielokrotności 3.
Krok 4) Krok 3 powtarzamy w ten sam sposób, aż do x= lub 5.
Krok 5) Pozostałe nieoznaczone liczby to liczby pierwsze od 2 do 25.
Pseudo kod
Begin Declare a boolean array of size n and initialize it to true For all numbers i : from 2 to sqrt(n) IF bool value of i is true THEN i is prime For all multiples of i (i<n) mark multiples of i as composite Print all unmarked numbers End
Sito Eratostenesa C/C++ kod Przykład
#include <iostream> #include <cstring> using namespace std; void Sieve_Of_Eratosthenes(int n) { // Create and initialize a boolean array bool primeNumber[n + 1]; memset(primeNumber, true, sizeof(primeNumber)); for (int j = 2; j * j <= n; j++) { if (primeNumber[j] == true) { // Update all multiples of i as false for (int k = j * j; k <= n; k += j) primeNumber[k] = false; } } for (int i = 2; i <= n; i++) if (primeNumber[i]) cout << i << " "; } int main() { int n = 25; Sieve_Of_Eratosthenes(n); return 0; }
Wyjście:
2 3 5 7 11 13 17 19 23
Sito Eratostenesa Python Przykład programu
def SieveOfEratosthenes(n): # Create a boolean array primeNumber = [True for i in range(n+2)] i = 2 while (i * i <= n): if (primeNumber[i] == True): # Update all multiples of i as false for j in range(i * i, n+1, i): primeNumber[j] = False i += 1 for i in range(2, n): if primeNumber[i]: print(i) n = 25 SieveOfEratosthenes(n)
Wyjście:
2 3 5 7 11 13 17 19 23
Segmentowe sito
Widzieliśmy, że Sito Eratostenesa jest wymagane do przeprowadzenia pętli przez cały zakres liczb. Zatem potrzebuje O(n) przestrzeni pamięci do przechowywania liczb. Sytuacja staje się skomplikowana, gdy próbujemy znaleźć liczby pierwsze w ogromnym zakresie. Nie jest wykonalne przydzielenie tak dużej przestrzeni pamięci dla większego n.
Algorytm można zoptymalizować, wprowadzając nowe funkcje. Pomysł polega na podzieleniu zakresu liczb na mniejsze segmenty i obliczeniu liczb pierwszych w tych segmentach jeden po drugim. Jest to wydajny sposób na zmniejszenie złożoności przestrzennej. Ta metoda nazywa się sito segmentowe.
Optymalizację można osiągnąć w następujący sposób:
- Użyj prostego sita, aby znaleźć liczby pierwsze od 2 do
i zapisz je w tablicy.
- Podziel zakres [0…n-1] na co najwyżej wiele segmentów
- Dla każdego segmentu powtórz go i zaznacz wielokrotność liczb pierwszych znalezionych w kroku 1. Ten krok wymaga O(
) przy maks.
Zwykłe sito wymaga O(n) przestrzeni pamięci pomocniczej, podczas gdy sito segmentowe wymaga O(), co jest dużym ulepszeniem dla dużego n. Metoda ta ma również wadę, ponieważ nie poprawia złożoności czasowej.
Analiza złożoności
Złożoność przestrzeni:
Algorytm prostego sita Eratostenesa wymaga przestrzeni pamięci O(n). A wymaga tego sito segmentowe
O() przestrzeń pomocnicza.
Złożoność czasowa:
Złożoność czasowa regularnego algorytmu sita Eratostenesa wynosi O(n*log(log(n)). Poniżej omówiono rozumowanie stojące za tą złożonością.
Dla danej liczby n czas potrzebny do oznaczenia liczby złożonej (tj. liczby niepierwszej) jest stały. Tak więc liczba przebiegów pętli jest równa-
n/2 + n/3 + n/5 + n/7 + ……∞
= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)
Harmoniczny postęp sumy liczb pierwszych można odliczyć jako log(log(n)).
(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))
Zatem złożoność czasowa będzie wynosić-
T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)
= n * log(log(n))
Zatem złożoność czasowa O(n * log(log(n)))
Następnie dowiesz się o Trójkąt Pascala
Podsumowanie
- Sito Eratostenesa filtruje liczby pierwsze w podanym górnym limicie.
- Filtrowanie liczby pierwszej rozpoczyna się od najmniejszej liczby pierwszej, „2”. Odbywa się to iteracyjnie.
- Iteracja jest wykonywana aż do pierwiastka kwadratowego z n, gdzie n jest danym zakresem liczb.
- Po tych iteracjach pozostałe liczby są liczbami pierwszymi.