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

De zeef van Eratosthenes is de eenvoudigste priemgetalzeef. Het is een priemgetalalgoritme om alle priemgetallen binnen een bepaalde limiet te doorzoeken. Er zijn verschillende priemgetalzeven. Bijvoorbeeld: de zeef van Eratosthenes, de zeef van Atkin, de zeef van Sundaram, enz.

Het woord "zeef” betekent een gebruiksvoorwerp dat stoffen filtert. Het zeefalgoritme is dus in Python en andere talen verwijst naar een algoritme om priemgetallen uit 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, viz., 1 en het nummer 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.

Zeef van Eratosthenes-algoritme

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

Zeef van Eratosthenes-algoritme

Algoritme Zeef van Eratosthenes

Hier is het algoritme voor de zeef van Eratosthenes:

Stap 1) Maak een lijst met getallen van 2 tot het opgegeven 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 overeenkomstige 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<=Algoritme Zeef van Eratosthenes).

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

n=a*b

Nogmaals, n =Algoritme Zeef van Eratosthenes*Algoritme Zeef van Eratosthenes

= (factor kleiner dan Algoritme Zeef van Eratosthenes) * (factor groter dan Zeef van Eratosthenes-algoritme)

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

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

Voorbeeld:

Laten we een voorbeeld nemen en kijken hoe het werkt.

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

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

Algoritme Zeef van Eratosthenes

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.

Zeef van Eratosthenes-algoritme

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.

Zeef van Eratosthenes-algoritme

Stap 4) We herhalen stap 3 op dezelfde manier tot x=Zeef van Eratosthenes-algoritme of 5.

Zeef van Eratosthenes-algoritme

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

Zeef van Eratosthenes-algoritme

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 hele getallenbereik moet laten lopen. Het heeft dus O(n) geheugenruimte nodig om de cijfers op te slaan. De situatie wordt ingewikkeld als we priemgetallen in een enorm bereik proberen te vinden. Het is niet haalbaar om zo'n grote geheugenruimte toe te wijzen aan een grotere n.

Het algoritme kan worden geoptimaliseerd door enkele nieuwe functies te introduceren. Het idee is om het getalbereik in kleinere segmenten te verdelen en priemgetallen in die segmenten één voor één te berekenen. Dit is een efficiënte manier om de ruimtevaart te verminderenplexiteit. Deze methode heet a gesegmenteerde zeef.

De optimalisatie kan in het volgende worden bereiktwing manier:

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

De reguliere zeef vereist O(n) extra geheugenruimte, terwijl de gesegmenteerde zeef O(Gesegmenteerde zeef), wat een grote verbetering is voor een grote n. De methode heeft ook een keerzijde omdat het de tijdcomm niet verbetertplexheid.

complexiteitsanalyse

Ruimte Complexiteit:

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

Tijd Complexiteit:

De tijd complexDe kwaliteit van een reguliere zeef van eratosthenes-algoritme is O(n*log(log(n))). De redenering achter deze complexwordt hieronder besproken.

Voor een gegeven getal n is de tijd die nodig is om een ​​samengesteld getal (dat wil zeggen niet-priemgetallen) 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 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))

Dus de tijd complexHet zal zijn-

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

= n * log(log(n))

Dus de tijd complexiteit O(n * log(log(n)))

Vervolgens leer je meer over Driehoek van Pascal

Samengevat

  • De Zeef van Eratosthenes filtert de priemgetallen binnen een bepaalde 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 zijn de overgebleven getallen de priemgetallen.