Sieve of Eratosthenes Algoritm: Python, C++ Exempelvis

By: Sarah Chen Sarah Chen
Hours Uppdaterad

The Sieve of Eratosthenes är den enklaste primtalssilen. Det är en primtalsalgoritm för att söka efter alla primtal i en given gräns. Det finns flera primtalssilar. Till exempel - Sieve of Eratosthenes, Sieve of Atkin, Sieve of Sundaram, etc.

Ordet "sikten” betyder ett redskap som filtrerar ämnen. Sållalgoritmen in Python och andra språk hänvisar till en algoritm för att filtrera bort primtal.

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

I sikten av Eratosthenes-metoden väljs ett litet primtal först, och alla multiplar av det filtreras bort. Processen körs på en slinga i ett givet intervall.

Till exempel:

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

Sieve of Eratosthenes Algorithm

Efter att ha applicerat Eratosthenessikten kommer den att producera listan med primtal 2, 3, 5, 7

Sieve of Eratosthenes Algorithm

Algoritm Sieve of Eratosthenes

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

Steg 1) Skapa en lista med siffror 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 på listan, x (ex är initialt lika med 2), gå igenom listan och filtrera motsvarande sammansatta siffror genom att markera alla multiplar av de valda talen.

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 av x ska vara mindre än eller lika med kvadratroten av n (x<=Algoritm Sieve of Eratosthenes).

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

n=a*b

Återigen, n =Algoritm Sieve of Eratosthenes*Algoritm Sieve of Eratosthenes

= (faktor mindre än Algoritm Sieve of Eratosthenes) * (faktor större än Sieve of Eratosthenes Algorithm)

Så åtminstone en av de främsta faktorer eller båda måste vara <=Algoritm Sieve of Eratosthenes. Alltså korsar till Algoritm Sieve of Eratosthenes kommer att räcka.

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

Exempelvis:

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

För 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 siffror från 2 till 25 eftersom vi valde n=25.

Algoritm Sieve of Eratosthenes

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

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

Sieve of Eratosthenes Algorithm

Notera: 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.

Sieve of Eratosthenes Algorithm

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

Sieve of Eratosthenes Algorithm

Steg 5) De återstående icke-markerade talen skulle vara primtalen från 2 till 25.

Sieve of Eratosthenes Algorithm

RELATERADE ARTIKLAR

Pseudo-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++ kod Exempel

#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

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 Sieve of Eratosthenes krävs för att köra en slinga genom hela talområdet. Den behöver alltså O(n) minnesutrymme för att lagra siffrorna. Situationen blir komplicerad när vi försöker hitta primtal i ett enormt intervall. Det är inte möjligt att tilldela ett så stort minnesutrymme 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 Segmenterad sil och lagra dem i en array.
  2. Dela upp området [0…n-1] i flera segment av storlek som mest Segmenterad sil
  3. För varje segment, iterera genom segmentet och markera multipeln av primtal som finns i steg 1. Detta steg kräver O(Segmenterad sil) vid max.

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

Komplexitetsanalys

Rymdkomplexitet:

Den enkla sikten av eratosthenes-algoritm kräver O(n) minnesutrymme. Och den segmenterade silen kräver
O(Komplexitetsanalys) hjälputrymme.

Tidskomplexitet:

Tidskomplexiteten för en vanlig sikt av eratosthenes-algoritm är O(n*log(log(n))). Resonemanget bakom denna komplexitet diskuteras nedan.

För ett givet tal n är tiden som krävs för att markera ett sammansatt tal (dvs icke-primtal) konstant. Så antalet gånger som slingan 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 primtal kan dras av som log(log(n)).

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

Så tidskomplexiteten kommer att vara-

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

= n * log(log(n))

Alltså tidskomplexiteten O(n * log(log(n)))

Därefter kommer du att lära dig om Pascals triangel

Sammanfattning

  • Silen av Eratosthenes filtrerar bort primtalen i en given övre gräns.
  • Filtrering av ett primtal börjar från det minsta primtal, "2". Detta görs iterativt.
  • Iterationen görs upp till kvadratroten ur n, där n är det givna talintervallet.
  • Efter dessa iterationer är talen som finns kvar primtalen.

Du kanske gillar: