Eratosthenes sikt i Python & C++

Vad är Eratosthenes sikt?

Eratosthenes-sikten är den enklaste primtalssikten. Det är en primtalsalgoritm som används för att upptäcka varje primtal inom en given gräns. Flera primtalssiktar finns, inklusive Eratosthenes-sikten, Atkins-sikten och Sundarams-sikten.

Ordet "sikten” hänvisar till ett redskap som filtrerar ämnen. I samma anda används silalgoritmen i Python och andra språk hänvisar till en metod som filtrerar bort primtal från en lista med heltal.

Denna algoritm filtrerar primtal med hjälp av en iterativ metod. Filtreringsprocessen börjar med det minsta primtalet. Ett primtal är ett naturligt tal större än 1 som bara har två delare, nämligen 1 och talet självt. Numbers som inte är primtal kallas sammansatta tal.

Varför använda Eratosthenes-sikten?

I Eratosthenes-sållen väljs först ett litet primtal, och alla multiplar av det filtreras bort. Processen körs i en loop över ett givet intervall och producerar varje primtal upp till n effektivt utan att utföra försöksdivision på varje kandidat.

Detta gör att sikten är snabbare än att kontrollera primalitet ett tal i taget. Den används ofta inom talteori, kryptografi, hashning och konkurrerande programmering där många primtal måste genereras snabbt.

Till exempel:

Låt oss ta talintervallet från 2 till 10.

Efter att ha applicerat Eratosthenes-sikten kommer den att producera listan med primtalen 2, 3, 5, 7.

Algoritm Sieve of Eratosthenes

Här är algoritmen för Sieve of Eratosthenes:

Steg 1) Skapa en lista med tal från 2 till det givna intervallet n. Vi börjar med 2 eftersom det är det minsta och första primtalet.

Steg 2) Välj det minsta talet i listan, x (initialt är x lika med 2), bläddra igenom listan och filtrera motsvarande sammansatta tal genom att markera alla multiplar av det valda talet.

Steg 3) Välj sedan nästa primtal eller det minsta omarkerade talet på listan och upprepa steg 2.

Steg 4) Upprepa föregående steg tills värdet på x är mindre än eller lika med kvadratroten ur n (x<=).

Obs: Det matematiska resonemanget är ganska enkelt. Talområdet n kan faktoriseras som:

n = a * b

Återigen, n = *

= (faktor mindre än ) * (faktor större än )

Så åtminstone en av de främsta faktorer eller båda måste vara <= Därför, att korsa upp till kommer att räcka.

Steg 5) Efter dessa fyra steg kommer de återstående omarketerade talen att vara alla primtal i det givna intervallet n.

Utarbetat exempel

Exempel:

Låt oss ta ett exempel och se hur det fungerar.

I det här exemplet hittar vi listan med primtal från 2 till 25. Så n = 25.

Steg 1) I det första steget tar vi en lista med tal från 2 till 25 eftersom vi valde n = 25.

Steg 2) Sedan väljer vi det minsta talet i listan, x. Ursprungligen är x = 2 eftersom det är det minsta primtalet. Sedan går vi igenom listan och markerar multiplarna av 2.

Multiplarerna av 2 för det givna värdet av n är: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Obs: Blå färg anger det valda numret och rosa färg anger de eliminerade multiplarna.

Steg 3) Sedan väljer vi det näst minsta omarkerade talet, som är 3, och upprepar det sista steget genom att markera multiplar av 3.

Steg 4) Vi upprepar steg 3 på samma sätt tills x = eller 5.

Steg 5) De återstående omarkerade talen är primtalen från 2 till 25.

Pseudo-Code

Följande pseudokod fångar den grundläggande strukturen för Eratosthenes såll innan vi översätter den till faktisk 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

Sil av Eratosthenes C/C++ Code Exempelvis

Nedan finns en komplett C++ implementering av Eratosthenes sil som skriver ut varje primtal upp till en vald övre gräns.

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

Produktion:

2 3 5 7 11 13 17 19 23

Sikt av Eratosthenes Python Programexempel

Följande Python Programmet implementerar samma algoritm med hjälp av en boolesk lista och en while-loop.

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)

Produktion:

2
3
5
7
11
13
17
19
23

Segmenterad sil

Vi har sett att Eratosthenes-sikten loopar genom hela talområdet. Därför behöver den O(n) minnesutrymme för att lagra talen. Situationen blir komplicerad när vi försöker hitta primtal i ett enormt talområde, eftersom det inte är möjligt att allokera ett så stort minnesblock för ett större n.

Algoritmen kan optimeras genom att introducera några nya funktioner. Tanken är att dela upp talområdet i mindre segment och beräkna primtal i dessa segment ett efter ett. Detta är ett effektivt sätt att minska utrymmets komplexitet. Denna metod kallas a segmenterad sil.

Optimeringen kan uppnås på följande sätt:

1. Använd en enkel sil för att hitta primtal från 2 till och lagra dem i en array.
2. Dela upp området [0…n-1] i flera segment av storlek som mest .
3. För varje segment, iterera genom segmentet och markera multiplarna av primtalen som hittades i steg 1. Detta steg kräver O() som max.

Den vanliga sikten kräver O(n) extra minnesutrymme, medan den segmenterade sikten kräver O(), vilket är en betydande förbättring för ett stort n. Metoden har också en nackdel, eftersom den inte förbättrar tidskomplexiteten.

Komplexitetsanalys

Att förstå både rums- och tidskomplexitet hjälper dig att välja mellan den vanliga sikten och den segmenterade sikten för en given problemstorlek.

Rymdkomplexitet:

Eratosthenes-algoritmens enkla sikt kräver O(n) minnesutrymme. Den segmenterade sikten kräver O() hjälputrymme.

Tidskomplexitet:

Tidskomplexiteten för en vanlig Eratosthenes-siktalgoritm är O(n*log(log(n))). Resonemanget bakom denna komplexitet diskuteras nedan.

För ett givet tal n är den tid som krävs för att markera ett sammansatt tal (det vill säga ett icke-primtal) konstant. Så antalet gånger loopen körs är lika med:

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

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

Den harmoniska progressionen av summan av primtalen kan härledas som log(log(n)):

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

Så tidskomplexiteten blir:

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

= n * log(log(n))

Således är tidskomplexiteten O(n * log(log(n))).

Härnäst kommer du att lära dig om Pascals triangel.

Vanliga frågor