Sigte af Eratosthenes-algoritme: Python, C++ Eksempel

Eratosthenes sigte er den enkleste primtalssigte. Det er en primtalsalgoritme til at søge i alle primtallene i en given grænse. Der er flere primtalssigter. For eksempel - Sieve of Eratosthenes, Sieve of Atkin, Sieve of Sundaram osv.

Ordet "sigte” betyder et redskab, der filtrerer stoffer. Således sigte-algoritmen ind Python og andre sprog refererer til en algoritme til at bortfiltrere primtal.

Denne algoritme frafiltrerer primtallet i en iterativ tilgang. Filtreringsprocessen starter med det mindste primtal. Et primtal er et naturligt tal, der er større end 1 og kun har to divisorer, nemlig 1 og selve tallet. De tal, der ikke er primtal, kaldes sammensatte tal.

I sigten af Eratosthenes-metoden vælges først et lille primtal, og alle multipla af det bliver filtreret fra. Processen kører på en løkke i et givet interval.

For eksempel:

Lad os tage talområdet fra 2 til 10.

Efter påføring af Eratosthenes Sieve, vil den producere listen over primtal 2, 3, 5, 7

Algoritme Sieve of Eratosthenes

Her er algoritmen til Sieve of Eratosthenes:

Trin 1) Opret en liste over tal fra 2 til det givne interval n. Vi starter med 2, da det er det mindste og første primtal.

Trin 2) Vælg det mindste tal på listen, x (i første omgang er x lig med 2), gå gennem listen, og filtrer de tilsvarende sammensatte tal ved at markere alle multipla af de 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 skal være mindre end eller lig med kvadratroden af n (x<=).

Bemærk: Den matematiske begrundelse er ret enkel. 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 <=. Således at krydse til vil være nok.

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

Eksempel:

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

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 over tal fra 2 til 25, da vi valgte n=25.

Trin 2) Så vælger vi det mindste tal på listen, x. Til at begynde med er x=2, da det er det mindste primtal. Så går vi gennem listen og markerer multipla af 2.

Multipletterne 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 ville 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

Si af 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;
}

Output:

2 3 5 7 11 13 17 19 23

Sigte af Eratosthener 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)

Output:

Segmenteret sigte

Vi har set, at Sieve of Eratosthenes er påkrævet for at køre en løkke gennem hele talområdet. Den har således brug for O(n) hukommelsesplads til at gemme tallene. Situationen bliver kompliceret, når vi forsøger at finde primtal i et stort område. Det er ikke muligt at allokere så stor en hukommelsesplads til en 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:

Brug en simpel sigte til at finde primtal fra 2 til og gem dem i et array.
Opdel området [0…n-1] i flere størrelsessegmenter
For hvert segment, gentag segmentet og marker multiplum af primtal fundet i trin 1. Dette trin kræver O() ved max.

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

Kompleksitetsanalyse

Rumkompleksitet:

Den simple sigte af eratosthenes-algoritme kræver O(n) hukommelsesplads. Og den segmenterede sigte kræver
O() hjælperum.

Tidskompleksitet:

Tidskompleksiteten af en regulær sigte af eratosthenes-algoritme er O(n*log(log(n))). Begrundelsen bag denne kompleksitet diskuteres nedenfor.

For et givet tal n er den tid, der kræves for at markere et sammensat tal (dvs. 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 trækkes 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))

Tidskompleksiteten O(n * log(log(n)))

Dernæst vil du lære om Pascals trekant

Resumé

Sieve of Eratosthenes frafiltrerer primtallene i en given øvre grænse.
Filtrering af et primtal starter fra det mindste primtal, "2". Dette gøres iterativt.
Iterationen udføres op til kvadratroden af n, hvor n er det givne talområde.
Efter disse iterationer er de tilbageværende tal primtallene.

Du kan lide: