Crivello di Eratostene in Python & C++

Che cos'è il crivello di Eratostene?

Il crivello di Eratostene è il più semplice crivello per numeri primi. Si tratta di un algoritmo utilizzato per scoprire tutti i numeri primi entro un dato limite. Esistono diversi crivelli per numeri primi, tra cui il crivello di Eratostene, il crivello di Atkin e il crivello di Sundaram.

La parola "setaccio" si riferisce a un utensile che filtra le sostanze. Nello stesso spirito, l'algoritmo del setaccio in Python e in altri linguaggi si riferisce a un metodo che filtra i numeri primi da un elenco di numeri interi.

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

Perché usare il crivello di Eratostene?

Nel metodo del crivello di Eratostene, si seleziona prima un piccolo numero primo e si filtrano tutti i suoi multipli. Il processo si ripete ciclicamente su un intervallo dato, producendo in modo efficiente tutti i numeri primi fino a n senza dover eseguire la divisione per tentativi su ciascun candidato.

Questo rende il crivello più veloce rispetto al controllo della primalità di un numero alla volta. È ampiamente utilizzato nella teoria dei numeri, nella crittografia, nell'hashing e nella programmazione competitiva, dove è necessario generare rapidamente molti numeri primi.

Per esempio:

Consideriamo l'intervallo numerico da 2 a 10.

Dopo aver applicato il Crivello di Eratostene, si otterrà l'elenco 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 n dato. Iniziamo con 2 perché è il più piccolo e il primo numero primo.

Passo 2) Seleziona il numero più piccolo nell'elenco, x (inizialmente x è uguale a 2), scorri l'elenco e filtra i numeri composti corrispondenti contrassegnando tutti i multipli del numero selezionato.

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

Passo 4) Ripeti il ​​passaggio precedente finché il valore di x non è minore o uguale alla radice quadrata di n (x<=).

Nota: Il ragionamento matematico è piuttosto 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 <= . Pertanto, attraversando fino a sarà sufficiente.

Passo 5) Dopo questi quattro passaggi, i numeri rimanenti non contrassegnati saranno tutti i numeri primi nell'intervallo n dato.

Esempio lavorato

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) Come primo passo, prenderemo un elenco di numeri da 2 a 25, dato che abbiamo scelto n = 25.

Passo 2) Quindi selezioniamo il numero più piccolo nell'elenco, x. Inizialmente x = 2 perché è il più piccolo numero primo. Poi scorriamo l'elenco e segniamo i multipli di 2.

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

Nota: Il colore blu indica il numero selezionato, mentre 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 nello stesso modo finché x = o 5.

Passo 5) I numeri rimanenti non contrassegnati sono i numeri primi da 2 a 25.

Pseudo-Code

Il seguente pseudocodice illustra la struttura di base del Crivello di Eratostene prima di tradurla in codice vero e proprio.

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++ Code Esempio

Di seguito è riportato un completo C++ Implementazione del Crivello di Eratostene che stampa ogni numero primo fino a un limite superiore scelto.

#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

Le seguenti Python Il programma implementa lo stesso algoritmo utilizzando una lista booleana e un ciclo while.

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 Crivello di Eratostene esegue un ciclo su tutto l'intervallo numerico. Pertanto, necessita di uno spazio di memoria O(n) per memorizzare i numeri. La situazione si complica quando si cerca di trovare i numeri primi in un intervallo molto ampio, perché non è fattibile allocare un blocco di memoria così grande per un n maggiore.

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, scorri il segmento e contrassegna i multipli dei numeri primi trovati 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(), il che rappresenta un miglioramento sostanziale per valori elevati di n. Il metodo presenta tuttavia anche uno svantaggio, in quanto non migliora la complessità temporale.

Analisi della complessità

Comprendere la complessità sia spaziale che temporale aiuta a scegliere tra il setaccio tradizionale e il setaccio segmentato in base alla dimensione del problema.

Complessità spaziale:

L'algoritmo del crivello di Eratostene semplice richiede uno spazio di memoria O(n). Il crivello segmentato richiede O() spazio ausiliario.

Complessità temporale:

La complessità temporale di un algoritmo standard del Crivello di Eratostene è O(n*log(log(n))). La motivazione di questa complessità è discussa di seguito.

Per un dato numero n, il tempo necessario per contrassegnare un numero composto (ovvero un numero non primo) è costante. Pertanto, il numero di volte in cui il ciclo viene eseguito è pari 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))

Pertanto la complessità temporale è O(n * log(log(n))).

Successivamente imparerai a conoscere Triangolo di Pascal.

DOMANDE FREQUENTI