Sito Eratostenesa w Python & C++

Czym jest sito Eratostenesa?

Sito Eratostenesa to najprostsze sito liczb pierwszych. Jest to algorytm liczb pierwszych, używany do znajdowania wszystkich liczb pierwszych w zadanym przedziale. Istnieje kilka sit pierwszych, w tym sito Eratostenesa, sito Atkinsa i sito Sundarama.

Słowo "sito„odnosi się do naczynia filtrującego substancje. W tym samym duchu algorytm sitowy w Python i innych językach odnosi się do metody, która filtruje liczby pierwsze z listy liczb całkowitych.

Ten algorytm filtruje liczby pierwsze, stosując podejście iteracyjne. Proces filtrowania rozpoczyna się od najmniejszej liczby pierwszej. Liczba pierwsza to liczba naturalna większa od 1, która ma tylko dwa dzielniki, mianowicie 1 i samą liczbę. Numbers liczby, które nie są liczbami pierwszymi, nazywane są liczbami złożonymi.

Dlaczego warto używać sita Eratostenesa?

W metodzie sita Eratostenesa najpierw wybierana jest mała liczba pierwsza, a następnie odfiltrowywane są wszystkie jej wielokrotności. Proces przebiega w pętli w danym zakresie, generując efektywnie każdą liczbę pierwszą do n bez konieczności wykonywania dzielenia próbnego dla każdego kandydata.

Dzięki temu sito działa szybciej niż sprawdzanie pierwszości liczb pojedynczo. Jest szeroko stosowane w teorii liczb, kryptografii, haszowaniu i programowaniu konkursowym, gdzie konieczne jest szybkie generowanie wielu liczb pierwszych.

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 wybranej liczby.

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 liczbowy n można rozłożyć na czynniki:

n = a * b

Ponownie, n = *

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

Zatem przynajmniej jeden z czynniki pierwsze lub oba muszą być <= . Dlatego też przechodząc do to wystarczy.

Krok 5) Po wykonaniu tych czterech kroków, pozostałe nieoznakowane liczby będą liczbami pierwszymi z danego zakresu n.

Przykład pracy

Przykład:

Przyjrzyjmy się bliżej 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 liczby 2 dla danej wartości n wynoszą: 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) Powtarzamy krok 3 w ten sam sposób, aż x = lub 5.

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

Rzekomy-Code

Poniższy pseudokod przedstawia podstawową strukturę Sita Eratostenesa przed jej przetłumaczeniem na rzeczywisty 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++ Code Przykład

Poniżej znajduje się kompletny C++ implementacja sita Eratostenesa, które drukuje wszystkie liczby pierwsze do wybranej górnej granicy.

#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

Poniższy Python Program implementuje ten sam algorytm, używając listy boolowskiej i pętli while.

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 tworzy pętlę w całym zakresie liczbowym. Dlatego potrzebuje O(n) przestrzeni pamięci do przechowywania liczb. Sytuacja komplikuje się, gdy próbujemy znaleźć liczby pierwsze w bardzo dużym zakresie, ponieważ nie jest możliwe przydzielenie tak dużego bloku 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 i zapisz je w tablicy.
2. Podziel zakres [0…n-1] na co najwyżej wiele segmentów .
3. Dla każdego segmentu powtórz go i zaznacz wielokrotności liczb pierwszych znalezionych w kroku 1. Ten krok wymaga O() maksymalnie.

Zwykłe sito wymaga O(n) przestrzeni pamięci pomocniczej, podczas gdy sito segmentowe wymaga O(), co stanowi znaczną poprawę w przypadku dużego n. Metoda ta ma jednak również wadę, ponieważ nie poprawia złożoności czasowej.

Analiza złożoności

Zrozumienie złożoności przestrzennej i czasowej pomaga dokonać wyboru między zwykłym sitem a sitem segmentowanym w przypadku danego rozmiaru problemu.

Złożoność przestrzeni:

Prosty algorytm Sito Eratostenesa wymaga O(n) przestrzeni pamięci. Sito segmentowane wymaga O(n)) przestrzeń pomocnicza.

Złożoność czasowa:

Złożoność czasowa standardowego algorytmu Sito Eratostenesa wynosi O(n*log(log(n)). Uzasadnienie tej złożoności omówiono poniżej.

Dla danej liczby n czas potrzebny na oznaczenie liczby złożonej (czyli liczby niepierwszej) jest stały. Zatem 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 wywnioskować 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 wynosi O(n * log(log(n))).

Następnie dowiesz się o Trójkąt Pascala.

FAQ