Sieve of Eratosthenes Algoritme: Python, C++ Eksempel

The Sieve of Eratosthenes er den enkleste primtallssilen. Det er en primtallsalgoritme for å søke i alle primtallene i en gitt grense. Det er flere primtallssikter. For eksempel - Sieve of Eratosthenes, Sieve of Atkin, Sieve of Sundaram, etc.

Ordet "sil” betyr et redskap som filtrerer stoffer. Dermed er silalgoritmen inn Python og andre språk refererer til en algoritme for å filtrere ut primtall.

Denne algoritmen filtrerer ut primtallet i en iterativ tilnærming. Filtreringsprosessen starter med det minste primtallet. Et primtal er et naturlig tall som er større enn 1 og har bare to divisorer, nemlig 1 og selve tallet. Tallene som ikke er primtall kalles sammensatte tall.

I sikten til Eratosthenes-metoden velges først et lite primtall, og alle multiplene av det blir filtrert ut. Prosessen kjører på en sløyfe i et gitt område.

For eksempel:

La oss ta tallområdet fra 2 til 10.

Etter å ha brukt Sieve of Eratosthenes, vil den produsere listen over primtall 2, 3, 5, 7

Algoritme Sieve of Eratosthenes

Her er algoritmen for Sieve of Eratosthenes:

Trinn 1) Lag en liste over tall fra 2 til det gitte området n. Vi starter med 2 da det er det minste og første primtallet.

Trinn 2) Velg det minste tallet på listen, x (til å begynne med er x lik 2), gå gjennom listen og filtrer de tilsvarende sammensatte tallene ved å merke alle multiplene av de valgte tallene.

Trinn 3) Velg deretter neste primtall eller det minste umerkede tallet på listen og gjenta trinn 2.

Trinn 4) Gjenta forrige trinn til verdien av x skal være mindre enn eller lik kvadratroten av n (x<=).

OBS: Det matematiske resonnementet er ganske enkelt. Tallområdet n kan faktoriseres som-

n=a*b

Igjen, n =*

= (faktor mindre enn ) * (faktor større enn )

Så minst en av de viktigste faktorer eller begge må være <=. Dermed krysser til vil være nok.

Trinn 5) Etter disse fire trinnene vil de gjenværende umerkede tallene være alle primtall på det gitte området n.

Eksempel:

La oss ta et eksempel og se hvordan det fungerer.

For dette eksempelet finner vi listen over primtall fra 2 til 25. Så n=25.

Trinn 1) I det første trinnet vil vi ta en liste med tall fra 2 til 25 ettersom vi valgte n=25.

Trinn 2) Deretter velger vi det minste tallet på listen, x. Til å begynne med er x=2 da det er det minste primtallet. Deretter går vi gjennom listen og merker multiplene av 2.

Multiplene av 2 for den gitte verdien av n er: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

OBS: Blå farge angir det valgte tallet, og rosa farge angir eliminerte multipler

Trinn 3) Deretter velger vi det nest minste umerkede tallet, som er 3, og gjentar det siste trinnet ved å merke multiplene av 3.

Trinn 4) Vi gjentar trinn 3 på samme måte til x= eller 5.

Trinn 5) De gjenværende ikke-merkede tallene vil være primtallene fra 2 til 25.

Pseudo-kode

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++ kode eksempel

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

Utgang:

2 3 5 7 11 13 17 19 23

Sil av Eratosthenes Python Program eksempel

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)

Utgang:

2
3
5
7
11
13
17
19
23

Segmentert sil

Vi har sett at Sieve of Eratosthenes er nødvendig for å kjøre en sløyfe gjennom hele tallområdet. Dermed trenger den O(n) minneplass for å lagre tallene. Situasjonen blir komplisert når vi prøver å finne primtal i et stort område. Det er ikke mulig å tildele en så stor minneplass for en større n.

Algoritmen kan optimaliseres ved å introdusere noen nye funksjoner. Ideen er å dele tallområdet inn i mindre segmenter og beregne primtall i disse segmentene en etter en. Dette er en effektiv måte å redusere plasskompleksiteten på. Denne metoden kalles a segmentert sil.

Optimaliseringen kan oppnås på følgende måte:

1. Bruk en enkel sil for å finne primtall fra 2 til og lagre dem i en rekke.
2. Del området [0...n-1] inn i flere segmenter av størrelse på det meste
3. For hvert segment, iterer gjennom segmentet og merk multiplum av primtall funnet i trinn 1. Dette trinnet krever O() ved maks.

Den vanlige sikten krever O(n) ekstra minneplass, mens den segmenterte sikten krever O(), som er en stor forbedring for en stor n. Metoden har en ulempe også fordi den ikke forbedrer tidskompleksiteten.

Kompleksitetsanalyse

Romkompleksitet:

Den enkle sikten av eratosthenes-algoritmen krever O(n) minneplass. Og den segmenterte silen krever
O() hjelperom.

Tidskompleksitet:

Tidskompleksiteten til en vanlig sikt av eratosthenes-algoritme er O(n*log(log(n))). Begrunnelsen bak denne kompleksiteten diskuteres nedenfor.

For et gitt tall n er tiden som kreves for å markere et sammensatt tall (dvs. ikke-primtall) konstant. Så antallet ganger løkken kjører er lik-

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

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

Den harmoniske progresjonen av summen av primtall kan trekkes fra som log(log(n)).

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

Så tidskompleksiteten vil være-

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

= n * log(log(n))

Dermed tidskompleksiteten O(n * log(log(n)))

Deretter vil du lære om Pascals trekant

Sammendrag

• Silen av Eratosthenes filtrerer ut primtallene i en gitt øvre grense.
• Filtrering av et primtall starter fra det minste primtall, "2". Dette gjøres iterativt.
• Iterasjonen gjøres opp til kvadratroten av n, der n er det gitte tallområdet.
• Etter disse iterasjonene er tallene som gjenstår primtallene.