Zeef van Eratosthenes-algoritme: Python, C++ Voorbeeld

De Zeef van Eratosthenes is de eenvoudigste zeef voor priemgetallen. Het is een algoritme voor priemgetallen om alle priemgetallen in een gegeven limiet te doorzoeken. Er zijn verschillende zeefsoorten voor priemgetallen. Bijvoorbeeld: de Zeef van Eratosthenes, Zeef van Atkin, Zeef van Sundaram, etc.

Het woord "zeef” betekent een gebruiksvoorwerp dat stoffen filtert. Het zeefalgoritme is dus in Python en andere talen verwijst naar een algoritme om priemgetallen eruit te filteren.

Dit algoritme filtert het priemgetal eruit in een iteratieve benadering. Het filterproces begint met het kleinste priemgetal. Een priemgetal is een natuurlijk getal dat groter is dan 1 en slechts twee delers heeft, namelijk 1 en het getal zelf. De getallen die geen priemgetallen zijn, worden samengestelde getallen genoemd.

In de zeef van de Eratosthenes-methode wordt eerst een klein priemgetal geselecteerd, en alle veelvouden ervan worden eruit gefilterd. Het proces loopt in een lus binnen een bepaald bereik.

Bijvoorbeeld:

Laten we het getallenbereik van 2 tot en met 10 nemen.

Na toepassing van de zeef van Eratosthenes zal het de lijst met priemgetallen 2, 3, 5, 7 opleveren

Algoritme Zeef van Eratosthenes

Hier is het algoritme voor de zeef van Eratosthenes:

Stap 1) Maak een lijst met getallen van 2 tot het gegeven bereik n. We beginnen met 2 omdat dit het kleinste en eerste priemgetal is.

Stap 2) Selecteer het kleinste getal in de lijst, x (aanvankelijk is x gelijk aan 2), doorloop de lijst en filter de bijbehorende samengestelde getallen door alle veelvouden van de geselecteerde getallen te markeren.

Stap 3) Kies vervolgens het volgende priemgetal of het kleinste ongemarkeerde getal in de lijst en herhaal stap 2.

Stap 4) Herhaal de vorige stap totdat de waarde van x kleiner moet zijn dan of gelijk is aan de vierkantswortel van n (x<=).

Opmerking: De wiskundige redenering is vrij eenvoudig. Het getalbereik n kan worden ontbonden als:

n=a*b

Nogmaals, n =*

= (factor kleiner dan ) * (factor groter dan )

Dus minstens één van de priemfactoren of beide moeten <= zijn. Dus doorkruisen naar zal genoeg zijn.

Stap 5) Na deze vier stappen zouden de resterende ongemarkeerde getallen alle priemgetallen in het gegeven bereik n zijn.

Voorbeeld:

Laten we een voorbeeld nemen en kijken hoe het werkt.

Voor dit voorbeeld zoeken we de lijst met priemgetallen van 2 tot en met 25. Dus n=25.

Stap 1) In de eerste stap nemen we een lijst met getallen van 2 tot en met 25, waarbij we n=25 hebben geselecteerd.

Stap 2) Vervolgens selecteren we het kleinste getal in de lijst, x. Aanvankelijk x=2 omdat dit het kleinste priemgetal is. Vervolgens doorkruisen we de lijst en markeren de veelvouden van 2.

De veelvouden van 2 voor de gegeven waarde van n zijn: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Opmerking: De blauwe kleur geeft het geselecteerde getal aan en de roze kleur geeft de geëlimineerde veelvouden aan

Stap 3) Vervolgens kiezen we het volgende kleinste ongemarkeerde getal, namelijk 3, en herhalen we de laatste stap door de veelvouden van 3 te markeren.

Stap 4) We herhalen stap 3 op dezelfde manier tot x= of 5.

Stap 5) De overige niet-gemarkeerde getallen zijn de priemgetallen van 2 tot en met 25.

Pseudo-code

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

Zeef van Eratosthenes C/C++ code Voorbeeld

#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;
} 

Output:

2 3 5 7 11 13 17 19 23

Zeef van Eratosthenes Python Programmavoorbeeld

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)

Output:

2
3
5
7
11
13
17
19
23

Gesegmenteerde zeef

We hebben gezien dat de Zeef van Eratosthenes een lus door het gehele getallenbereik moet laten lopen. Daarom is er O(n) geheugenruimte nodig om de getallen op te slaan. De situatie wordt ingewikkeld als we proberen priemgetallen in een enorm bereik te vinden. Het is niet haalbaar om zo'n grote geheugenruimte toe te wijzen aan een grotere n.

Het algoritme kan worden geoptimaliseerd door een aantal nieuwe functies te introduceren. Het idee is om het getallenbereik in kleinere segmenten te verdelen en priemgetallen in die segmenten één voor één te berekenen. Dit is een efficiënte manier om de ruimtecomplexiteit te verminderen. Deze methode wordt een gesegmenteerde zeef.

Optimalisatie kan op de volgende manier worden bereikt:

1. Gebruik een eenvoudige zeef om priemgetallen van 2 tot en met XNUMX te vinden. en sla ze op in een array.
2. Verdeel het bereik [0…n-1] in maximaal meerdere segmenten van grootte
3. Loop voor elk segment door het segment en markeer het veelvoud van de priemgetallen die u in stap 1 hebt gevonden. Voor deze stap is O( nodig) bij max.

De reguliere zeef vereist O(n) extra geheugenruimte, terwijl de gesegmenteerde zeef O(), wat een grote verbetering is voor een grote n. De methode heeft ook een nadeel, omdat het de tijdscomplexiteit niet verbetert.

Complexiteitsanalyse

Ruimtecomplexiteit:

Het eenvoudige zeef-van-eratosthenes-algoritme vereist O(n) geheugenruimte. En de gesegmenteerde zeef vereist
O() hulpruimte.

Tijdscomplexiteit:

De tijdcomplexiteit van een reguliere zeef van het Eratosthenes-algoritme is O(n*log(log(n))). De redenering achter deze complexiteit wordt hieronder besproken.

Voor een gegeven getal n is de tijd die nodig is om een ​​samengesteld getal (d.w.z. niet-priemgetallen) te markeren constant. Dus het aantal keren dat de lus wordt uitgevoerd is gelijk aan-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

De harmonische progressie van de som van de priemgetallen kan worden afgetrokken als log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

De tijdcomplexiteit zal dus zijn-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Dus de tijdcomplexiteit O(n * log(log(n)))

Vervolgens leer je meer over Driehoek van Pascal

Samenvatting

• De zeef van Eratosthenes filtert de priemgetallen binnen een gegeven bovengrens eruit.
• Het filteren van een priemgetal begint vanaf het kleinste priemgetal, “2”. Dit gebeurt iteratief.
• De iteratie wordt uitgevoerd tot aan de vierkantswortel van n, waarbij n het gegeven getalbereik is.
• Na deze iteraties blijven de priemgetallen over.