Algoritmo del crivello di Eratostene: Python, C++ Esempio

Il crivello di Eratostene è il crivello dei numeri primi più semplice. È un algoritmo di numeri primi per cercare tutti i numeri primi entro un dato limite. Esistono diversi setacci di numeri primi. Ad esempio: il Setaccio di Eratostene, il Setaccio di Atkin, il Setaccio di Sundaram, ecc.

La parola "setaccio" significa un utensile che filtra le sostanze. Pertanto, l'algoritmo del setaccio in Python e altre lingue si riferiscono a un algoritmo per filtrare i numeri primi.

Questo algoritmo filtra il numero primo in un approccio iterativo. Il processo di filtraggio inizia con il numero primo più piccolo. Un primo è un numero naturale maggiore di 1 e ha solo due divisori, vale a dire 1 e il numero stesso. I numeri che non sono primi sono chiamati numeri composti.

Nel crivello del metodo Eratostene, viene selezionato prima un numero primo piccolo e tutti i suoi multipli vengono filtrati. Il processo viene eseguito su un ciclo in un determinato intervallo.

Per esempio:

Prendiamo l'intervallo di numeri da 2 a 10.

Dopo aver applicato il Setaccio di Eratostene, produrrà la lista dei numeri primi 2, 3, 5, 7

Algoritmo Setaccio di Eratostene

Ecco l'algoritmo per il Setaccio di Eratostene:

Passo 1) Crea un elenco di numeri da 2 all'intervallo indicato n. Iniziamo con 2 poiché è il più piccolo e il primo numero primo.

Passo 2) Seleziona il numero più piccolo nell'elenco, x (inizialmente x è uguale a 2), attraversa l'elenco e filtra i numeri compositi corrispondenti contrassegnando tutti i multipli dei numeri selezionati.

Passo 3) Quindi scegli il numero primo successivo o il numero non contrassegnato più piccolo nell'elenco e ripeti il ​​passaggio 2.

Passo 4) Ripetere il passaggio precedente finché il valore di x non sarà inferiore o uguale alla radice quadrata di n (x<=).

Nota: Il ragionamento matematico è abbastanza semplice. L'intervallo numerico n può essere fattorizzato come-

n=a*b

Ancora una volta, n =*

= (fattore minore di ) * (fattore maggiore di )

Quindi almeno uno dei fattori primari oppure entrambi devono essere <=. Quindi, attraversando sarà sufficiente.

Passo 5) Dopo questi quattro passaggi, i restanti numeri non contrassegnati sarebbero tutti i numeri primi di quel dato intervallo n.

Esempio:

Facciamo un esempio e vediamo come funziona.

Per questo esempio troveremo l'elenco dei numeri primi da 2 a 25. Quindi n=25.

Passo 1) Nel primo passaggio, prenderemo un elenco di numeri da 2 a 25 poiché abbiamo selezionato n=25.

Passo 2) Quindi selezioniamo il numero più piccolo nell'elenco, x. Inizialmente x=2 poiché è il numero primo più piccolo. Quindi attraversiamo l'elenco e contrassegniamo i multipli di 2.

I multipli di 2 per il dato valore di n sono: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Nota: Il colore blu indica il numero selezionato e il colore rosa indica i multipli eliminati

Passo 3) Quindi scegliamo il successivo numero non contrassegnato più piccolo, che è 3, e ripetiamo l'ultimo passaggio contrassegnando i multipli di 3.

Passo 4) Ripetiamo il passaggio 3 allo stesso modo fino a x= o 5.

Passo 5) I restanti numeri non contrassegnati sarebbero i numeri primi da 2 a 25.

Pseudo-codice

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

Setaccio di Eratostene C/C++ codice Esempio

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

Produzione:

2 3 5 7 11 13 17 19 23

Setaccio di Eratostene Python Esempio di programma

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)

Produzione:

2
3
5
7
11
13
17
19
23

Setaccio segmentato

Abbiamo visto che il Setaccio di Eratostene deve eseguire un ciclo attraverso l'intero intervallo numerico. Pertanto, ha bisogno di O(n) spazio di memoria per memorizzare i numeri. La situazione diventa complicata quando cerchiamo di trovare numeri primi in un intervallo molto vasto. Non è possibile allocare uno spazio di memoria così grande per un n più grande.

L'algoritmo può essere ottimizzato introducendo alcune nuove funzionalità. L'idea è di dividere l'intervallo numerico in segmenti più piccoli e calcolare i numeri primi in quei segmenti uno per uno. Questo è un modo efficiente per ridurre la complessità dello spazio. Questo metodo è chiamato setaccio segmentato.

L'ottimizzazione può essere ottenuta nel modo seguente:

1. Usa un semplice setaccio per trovare i numeri primi da 2 a e memorizzarli in un array.
2. Dividere l'intervallo [0...n-1] in più segmenti di dimensione massima
3. Per ogni segmento, scorrere il segmento e contrassegnare il multiplo dei numeri primi trovato nel passaggio 1. Questo passaggio richiede O() al massimo

Il crivello normale richiede O(n) spazio di memoria ausiliaria, mentre il crivello segmentato richiede O(), che è un grande miglioramento per un grande n. Il metodo ha anche uno svantaggio perché non migliora la complessità temporale.

Analisi della complessità

Complessità spaziale:

Il semplice algoritmo del crivello di eratostene richiede O(n) spazio di memoria. E il setaccio segmentato richiede
O() spazio ausiliario.

Complessità temporale:

La complessità temporale di un algoritmo regolare del crivello di Eratostene è O(n*log(log(n))). Il ragionamento alla base di questa complessità è discusso di seguito.

Per un dato numero n, il tempo necessario per contrassegnare un numero composto (cioè numeri non primi) è costante. Quindi, il numero di volte in cui il ciclo viene eseguito è uguale a-

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

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

La progressione armonica della somma dei numeri primi può essere dedotta come log(log(n)).

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

Quindi, la complessità temporale sarà-

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

= n * log(log(n))

Quindi la complessità temporale O(n * log(log(n)))

Successivamente imparerai a conoscere Triangolo di Pascal

Sommario

• Il Setaccio di Eratostene filtra i numeri primi entro un dato limite superiore.
• Il filtraggio di un numero primo inizia dal numero primo più piccolo, “2”. Questo viene fatto in modo iterativo.
• L'iterazione viene eseguita fino alla radice quadrata di n, dove n è l'intervallo numerico specificato.
• Dopo queste iterazioni, i numeri che rimangono sono i numeri primi.