Eratosthenes' si i Python & C++

Hvad er Eratosthenes' si?

Eratosthenes-sigten er den enkleste primtalssigte. Det er en primtalsalgoritme, der bruges til at opdage ethvert primtal inden for en given grænse. Der findes adskillige primtalssigter, herunder Eratosthenes-sigten, Atkins-sigten og Sundarams-sigten.

Ordet "sigte" henviser til et redskab, der filtrerer stoffer. I samme ånd anvendes sialgoritmen i Python og andre sprog refererer til en metode, der filtrerer primtal fra en liste af heltal.

Denne algoritme filtrerer primtal ved hjælp af en iterativ tilgang. Filtreringsprocessen starter med det mindste primtal. Et primtal er et naturligt tal større end 1, der kun har to divisorer, nemlig 1 og selve tallet. Numbers der ikke er primtal, kaldes sammensatte tal.

Hvorfor bruge Eratosthenes-sigten?

I Eratosthenes-si-metoden vælges et lille primtal først, og alle multipla af det filtreres fra. Processen kører i en løkke på tværs af et givet interval, hvor hvert primtal op til n produceres effektivt uden at udføre prøvedivision på hver kandidat.

Dette gør sigten hurtigere end at kontrollere primtal ét tal ad gangen. Den bruges i vid udstrækning i talteori, kryptografi, hashing og konkurrencepræget programmering, hvor mange primtal skal genereres hurtigt.

For eksempel:

Lad os tage talområdet fra 2 til 10.

Efter at have anvendt Eratosthenes' si, vil den producere listen over primtallene 2, 3, 5, 7.

Algoritme Sieve of Eratosthenes

Her er algoritmen til Sieve of Eratosthenes:

Trin 1) Lav en liste med tal fra 2 til det givne talområde n. Vi starter med 2, fordi det er det mindste og første primtal.

Trin 2) Vælg det mindste tal på listen, x (i starten er x lig med 2), gennemgå listen, og filtrer de tilsvarende sammensatte tal ved at markere alle multipla af det valgte tal.

Trin 3) Vælg derefter det næste primtal eller det mindste umarkerede tal på listen, og gentag trin 2.

Trin 4) Gentag det forrige trin, indtil værdien af ​​x er mindre end eller lig med kvadratroden af ​​n (x <=).

Bemærk: Den matematiske argumentation er ret simpel. Talområdet n kan faktoriseres som:

n = a * b

Igen, n = *

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

Så i hvert fald en af ​​de primære faktorer eller begge skal være <= Derfor, at krydse op til vil være nok.

Trin 5) Efter disse fire trin vil de resterende umarkerede tal være alle primtallene i det givne område n.

Bearbejdet eksempel

Eksempel:

Lad os tage et eksempel og se, hvordan det fungerer.

I dette eksempel finder vi listen over primtal fra 2 til 25. Så n = 25.

Trin 1) I det første trin tager vi en liste med tal fra 2 til 25, da vi valgte n = 25.

Trin 2) Så vælger vi det mindste tal på listen, x. I starten er x = 2, fordi det er det mindste primtal. Så går vi gennem listen og markerer multiplaerne af 2.

Multiplarne af 2 for den givne værdi af n er: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Bemærk: Blå farve angiver det valgte tal, og lyserød farve angiver de eliminerede multipla.

Trin 3) Derefter vælger vi det næstmindste umarkerede tal, som er 3, og gentager det sidste trin ved at markere multiplerne af 3.

Trin 4) Vi gentager trin 3 på samme måde, indtil x = eller 5.

Trin 5) De resterende ikke-markerede tal er primtallene fra 2 til 25.

pseudoCode

Den følgende pseudokode indfanger den grundlæggende struktur af Eratosthenes-sigten, før vi oversætter den til faktisk 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

Si af Eratosthenes C/C++ Code Eksempel

Nedenfor er en komplet C++ Implementering af Eratosthenes' si, der udskriver ethvert primtal op til en valgt øvre grænse.

#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

Sigte af Eratosthener Python Program eksempel

Følgende Python Programmet implementerer den samme algoritme ved hjælp af en boolsk liste og en while-løkke.

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

Segmenteret sigte

Vi har set, at Eratosthenes' si løber en løkke gennem hele talområdet. Derfor behøver den O(n) hukommelsesplads til at gemme tallene. Situationen bliver kompliceret, når vi forsøger at finde primtal i et enormt talområde, fordi det ikke er muligt at allokere en så stor hukommelsesblok til et større n.

Algoritmen kan optimeres ved at introducere nogle nye funktioner. Ideen er at opdele talområdet i mindre segmenter og beregne primtal i disse segmenter én efter én. Dette er en effektiv måde at reducere rummets kompleksitet. Denne metode kaldes en segmenteret sigte.

Optimeringen kan opnås på følgende måde:

1. Brug en simpel sigte til at finde primtal fra 2 til og gem dem i et array.
2. Opdel området [0…n-1] i flere størrelsessegmenter .
3. For hvert segment iterer du gennem segmentet og markerer multiplerne af primtallene fundet i trin 1. Dette trin kræver O() maksimalt.

Den almindelige sigte kræver O(n) ekstra hukommelsesplads, hvorimod den segmenterede sigte kræver O(), hvilket er en betydelig forbedring for et stort n. Metoden har også en ulempe, fordi den ikke forbedrer tidskompleksiteten.

Kompleksitetsanalyse

At forstå både rum- og tidskompleksitet hjælper dig med at vælge mellem den almindelige si og den segmenterede si til en given problemstørrelse.

Rumkompleksitet:

Den simple Eratosthenes-sigtealgoritme kræver O(n) hukommelsesplads. Den segmenterede sigte kræver O() hjælperum.

Tidskompleksitet:

Tidskompleksiteten af ​​en regulær Eratosthenes-sigtealgoritme er O(n*log(log(n))). Ræsonnementet bag denne kompleksitet diskuteres nedenfor.

For et givet tal n er den tid, der kræves for at markere et sammensat tal (dvs. et ikke-primtal), konstant. Så antallet af gange løkken kører er lig med:

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

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

Den harmoniske progression af summen af ​​primtallene kan udledes 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))

Således er tidskompleksiteten O(n * log(log(n))).

Dernæst vil du lære om Pascals trekant.

Ofte Stillede Spørgsmål