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.

Algorytm sita Eratostenesa

Po zastosowaniu sita Eratostenesa otrzymamy listę liczb pierwszych 2, 3, 5, 7

Algorytm sita Eratostenesa

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<=Algorytm sita Eratostenesa).

Uwaga: Rozumowanie matematyczne jest dość proste. Zakres liczb n można rozłożyć na czynniki jako:

n=a*b

Ponownie, n =Algorytm sita Eratostenesa*Algorytm sita Eratostenesa

= (współczynnik mniejszy niż Algorytm sita Eratostenesa) * (współczynnik większy niż Algorytm sita Eratostenesa)

Zatem przynajmniej jeden z czynniki pierwsze lub oba muszą być <=Algorytm sita Eratostenesa. Zatem przejazd do Algorytm sita Eratostenesa 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.

Algorytm sita Eratostenesa

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.

Algorytm sita Eratostenesa

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.

Algorytm sita Eratostenesa

Krok 4) Krok 3 powtarzamy w ten sam sposób, aż do x=Algorytm sita Eratostenesa lub 5.

Algorytm sita Eratostenesa

Krok 5) Pozostałe nieoznaczone liczby to liczby pierwsze od 2 do 25.

Algorytm sita Eratostenesa

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:

  1. Użyj prostego sita, aby znaleźć liczby pierwsze od 2 do Segmentowe sito i zapisz je w tablicy.
  2. Podziel zakres [0…n-1] na co najwyżej wiele segmentów Segmentowe sito
  3. Dla każdego segmentu powtórz go i zaznacz wielokrotność liczb pierwszych znalezionych w kroku 1. Ten krok wymaga O(Segmentowe sito) przy maks.

Zwykłe sito wymaga O(n) przestrzeni pamięci pomocniczej, podczas gdy sito segmentowe wymaga O(Segmentowe sito), 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(Analiza złożoności) 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.