Zeef van Eratosthenes in Python & C++

Wat is de zeef van Eratosthenes?

De zeef van Eratosthenes is de eenvoudigste priemgetallenzeef. Het is een priemgetallenalgoritme dat gebruikt wordt om alle priemgetallen binnen een bepaalde limiet te vinden. Er bestaan ​​verschillende priemgetallenzeven, waaronder de zeef van Eratosthenes, de zeef van Atkin en de zeef van Sundaram.

Het woord "zeef" verwijst naar een werktuig dat stoffen filtert. In dezelfde geest verwijst het zeefalgoritme in Python In andere talen verwijst het naar een methode die priemgetallen uit een lijst met gehele getallen filtert.

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

Waarom de zeef van Eratosthenes gebruiken?

Bij de zeefmethode van Eratosthenes wordt eerst een klein priemgetal geselecteerd, waarna alle veelvouden daarvan worden weggefilterd. Het proces wordt in een lus uitgevoerd over een bepaald bereik, waarbij alle priemgetallen tot en met n efficiënt worden gegenereerd zonder dat voor elke kandidaat een proefdeling hoeft te worden uitgevoerd.

Dit maakt de zeefmethode sneller dan het controleren op primaliteit van één getal tegelijk. De methode wordt veel gebruikt in de getaltheorie, cryptografie, hashing en competitief programmeren, waar snel veel priemgetallen gegenereerd moeten worden.

Bijvoorbeeld:

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

Na toepassing van de zeef van Eratosthenes levert dit de lijst met priemgetallen 2, 3, 5, 7 op.

Algoritme Zeef van Eratosthenes

Hier is het algoritme voor de zeef van Eratosthenes:

Stap 1) Maak een lijst met getallen van 2 tot en met 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 het geselecteerde getal 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 is dan of gelijk aan de wortel van n (x<=).

Let op: De wiskundige redenering is vrij eenvoudig. Het getallenbereik n kan als volgt worden ontbonden:

n = a * b

Nogmaals, n = *

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

Dus minstens één van de priemfactoren of beide moeten <= zijn Daarom, door omhoog te gaan naar zal genoeg zijn.

Stap 5) Na deze vier stappen zullen de overgebleven, niet-gemarkeerde getallen alle priemgetallen in het gegeven bereik n zijn.

Uitgewerkt voorbeeld

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 op. Dus n = 25.

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

Stap 2) Vervolgens selecteren we het kleinste getal uit de lijst, x. Aanvankelijk is x = 2, omdat dit het kleinste priemgetal is. Daarna doorlopen we de lijst en markeren we 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.

Let op: Blauw geeft het geselecteerde getal aan, en roze geeft de uitgesloten 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 totdat x = of 5.

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

Pseudo-Code

De volgende pseudocode geeft de basisstructuur van de Zeef van Eratosthenes weer voordat we deze naar daadwerkelijke code vertalen.

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

Hieronder staat een complete C++ Implementatie van de Zeef van Eratosthenes die alle priemgetallen tot een gekozen bovengrens afdrukt.

#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

De volgende Python Het programma implementeert hetzelfde algoritme met behulp van een booleanlijst en een while-lus.

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 hele getallenbereik doorloopt. Daarom is er O(n) geheugenruimte nodig om de getallen op te slaan. De situatie wordt ingewikkeld wanneer we priemgetallen in een enorm bereik proberen te vinden, omdat het niet haalbaar is om zo'n groot geheugenblok toe te wijzen voor 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. Doorloop elk segment en markeer de veelvouden van de priemgetallen die in stap 1 zijn gevonden. Deze stap vereist O() maximaal.

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

Complexiteitsanalyse

Inzicht in zowel ruimtelijke als temporele complexiteit helpt je bij het kiezen tussen de reguliere zeefmethode en de gesegmenteerde zeefmethode voor een gegeven probleemgrootte.

Ruimtecomplexiteit:

Het eenvoudige zeefalgoritme van Eratosthenes vereist O(n) geheugenruimte. De gesegmenteerde zeef vereist O() hulpruimte.

Tijdscomplexiteit:

De tijdscomplexiteit van een standaard Zeef van 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 (dat wil zeggen, een niet-priemgetal) te markeren constant. Het aantal keren dat de lus wordt uitgevoerd is dus gelijk aan:

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

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

De harmonische reeks van de som van de priemgetallen kan worden afgeleid als log(log(n)):

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

De tijdscomplexiteit zal dus zijn:

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

= n * log(log(n))

De tijdscomplexiteit is dus O(n * log(log(n))).

Vervolgens leer je meer over Driehoek van Pascal.

Veelgestelde vragen