Setaccio di Eratostene con C ++

Un numero primo è un numero naturale (intero) che è maggiore o uguale a due, che può essere diviso solo da solo e 1. I primi numeri primi sono: 2, 3, 5, 7, ecc.

Per il numero 5, il numero di numeri primi che sono fino a e/o intendo 5 sono:

2, 3, 5

Per il numero 8, il numero di numeri primi che sono fino a e/o intendo 8 sono:

2, 3, 5, 7

Per il numero 19, il numero di numeri primi che sono fino a e/o intendo 19 sono:

2, 3, 5, 7, 11, 13, 17, 19

Per il numero 25, il numero di numeri primi che sono fino a e/o intendo 25 sono:

2, 3, 5, 7, 11, 13, 17, 19, 23

Per il numero 36, il numero di numeri primi che sono fino a e/o intendo 36 sono:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Per il numero 37, il numero di numeri primi che sono fino a e/o tra cui 37 sono:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Questi elenchi sono solo esempi. Esistono molti altri elenchi di numeri primi e/o inclusi un determinato numero. Inizia la comprensione del setaccio di Eratoshene rilevando che i numeri primi al di sotto di un numero più piccolo sono gli stessi della prima parte dei numeri primi sotto un dato numero maggiore.

Il setaccio di Eratostene è una tecnica per trovare tutti i numeri primi che sono inferiori o uguali a un determinato numero come 36 o 37 sopra. Questo numero come 36 o 37 viene generalmente dato il nome variabile "N" nella programmazione. Il setaccio di Eratostene è considerato un algoritmo efficiente per ottenere l'elenco dei numeri primi.

Dimostrazione per setaccio di Eratostene

La domanda è: trova i numeri primi inferiori o uguali a 5, ad esempio, in modo efficiente. Il modo efficiente qui significa utilizzare il minor numero di operazioni possibile. I numeri primi iniziano da 2. Tutti i numeri inclusi i multipli di piccoli numeri primi da 2 a 5 sono:

2, 3, 4, 5

In questo intervallo, un numero che non è un numero primo è un multiplo di un numero primo precedente. Un multiplo può essere ottenuto mediante aggiunta dello stesso numero primo, più e più volte. Ad esempio, 2 + 2 è 4, più 2 è di nuovo 6. E questo continua oltre la gamma. Quattro, che è un multiplo di 2, non dovrebbero essere nell'elenco perché non è un numero primo. L'equazione 3 + 3 è 6, che è già oltre l'intervallo. E 6 o qualsiasi numero oltre l'intervallo non dovrebbe essere nell'elenco. Quindi, il risultato è il seguente:

2, 3, 5

Il numero in questione qui è 5. La radice quadrata di 5 è 2.24. Il valore intero per la radice quadrata di 5 è 2. I multipli dei numeri primi sotto e fino a 2, che è il valore intero per la radice quadrata di 5, vengono rimossi dall'elenco di tutti i numeri.

Considera ora, il numero 8. Tutti i numeri inclusi i multipli di piccoli numeri primi da 2 a 8 sono:

2, 3, 4, 5, 6, 7, 8

L'equazione 2 + 2 è 4. Quattro esce. L'equazione 4+2 è 6. Sei esce. L'equazione 6 + 2 è 8. Otto è fuori. Il prossimo numero primo da considerare è 3. L'equazione 3 + 3 è 6. Sei sono già esclusi dalla continua aggiunta di 2. L'equazione 6 + 3 è 9; Questo è fuori portata. I numeri primi tra 2 e 8, inclusi, sono:

2, 3, 5, 7

Il numero in questione qui è 8. La radice quadrata di 8 è 2.83. Il valore intero per la radice quadrata di 8 è 2. I multipli dei numeri primi sotto e fino a 2 che è il valore intero per la radice quadrata di 8 vengono rimossi per ottenere l'elenco richiesto dei numeri primi.

Un problema simile è quello di elencare i numeri primi da 2 a 19, inclusivamente. Tutti i numeri da 2 a 19, compresi sono:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

L'equazione 2 + 2 è 4; 4 è fuori. L'equazione 4 + 2 è 6; 6 è fuori. L'equazione 6 + 2 è 8; 8 è fuori. L'equazione 8 + 2 è 10; 10 è fuori. L'equazione 10 + 2 è 12; 12 è fuori. L'equazione 12 + 2 è 14; 14 è fuori. L'equazione 14 + 2 è 16; 16 è fuori. L'equazione 16 + 2 è 18; 18 è fuori. L'equazione 18 + 2 è 20, che è al di sopra della gamma; 20 è fuori.

Il prossimo numero primo da considerare, salire verso l'alto verso la radice quadrata di 19, è 3. L'equazione 3 + 3 è 6; 6 è già escluso come un multiplo di 2. L'equazione 6 + 3 è 9; 9 esce. L'equazione 9 + 3 è 12; 12 è già escluso come un multiplo di 2. L'equazione 12 + 3 è 15; 15 è fuori. L'equazione 15 + 3 è 18; 18 è già escluso come un multiplo di 2. L'equazione 18 + 3 è 21, che è al di sopra della gamma. Il risultato è:

2, 3, 5, 7, 11, 13, 17, 19

Il numero in questione qui è 19. La radice quadrata di 19 è 4.36. Il valore intero per la radice quadrata di 19 è 4. I multipli di numeri primi sotto e fino a 4 che è il valore intero per la radice quadrata di 19.

I numeri primi sotto e fino a 4 sono: 2 e 3. A causa di 3, non ha senso rimuovere i numeri 6, 12 e 18 che sono multipli di 3, che sono già rimossi come multipli di 2. Solo i multipli di 3 che non sono multipli di 2 vengono rimossi a causa di 3. In pratica, dopo aver rimosso i multipli di 2, solo i multipli da e sopra 3 x 3 = 9 dovrebbero essere rimossi senza ripetere la rimozione di 6. A causa di 3, i numeri da rimuovere sono 9, 12, 15 e 18; con 12 e 18 rimossi due volte in teoria. Il numero 6 deve essere rimosso una volta e non due volte.

Sia N 25, un nuovo numero in questione. Tutti i numeri da 2 a 25 sono:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

L'equazione 2 + 2 è 4; 4 esce. L'equazione 4 + 2 è 6; 6 è fuori. L'equazione 6 + 2 è 8; 8 è fuori. L'equazione 8 + 2 è 10; 10 è fuori. L'equazione 10 + 2 è 12; 12 è fuori. L'equazione 12 + 2 è 14; 14 è fuori. L'equazione 14 + 2 è 16; 16 è fuori. L'equazione 16 + 2 è 18; 18 è fuori. L'equazione 18 + 2 è 20; 20 è fuori. L'equazione 20 + 2 è 22; 22 è fuori. L'equazione 22 + 2 è 24; 24 è fuori. L'equazione 24 + 2 è 26, che è al di sopra della gamma.

Il prossimo numero primo da considerare, salire verso l'alto verso la radice quadrata di 25, è 3. L'equazione 3 + 3 è 6; 6 è già escluso come un multiplo di 2. L'equazione 6 + 3 è 9; 9 esce. L'equazione 9 + 3 è 12. Dodici sono già esclusi come un multiplo di 2. L'equazione 12 + 3 è 15; 15 è fuori. L'equazione 15 + 3 è 18; 18 è già escluso come un multiplo di 2. L'equazione 18 + 3 è 21; 21 esce. L'equazione 21 + 3 è 24; 24 è già escluso come un multiplo di 2. L'equazione 24 + 3 è 27, che è al di sopra dell'intervallo.

Il prossimo numero primo da considerare, salire verso l'alto verso la radice quadrata di 25 che è 5, è 5. L'equazione 5 + 5 è 10; 10 è già escluso come un multiplo di 2. L'equazione 10 + 5 è 15; 15 è già escluso come un multiplo di 3. L'equazione 15 + 5 è 20; 20 è già escluso come un multiplo di 2. L'equazione 20 + 5 è 25; 25 esce. Il risultato è:

2, 3, 5, 7, 11, 13, 17, 19, 23

Il numero in questione qui è 25. La radice quadrata di 25 è 5. Il valore intero per la radice quadrata di 25 è 5. Vengono rimossi i multipli di numeri primitivi sotto e fino a 5, che è il valore intero per la radice quadrata di 25,.

I numeri primi sotto e fino a 5 sono 2, 3 e 5. A causa di 2, i numeri che dovrebbero essere rimossi dall'elenco di tutti i numeri per multipli sono: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 e 24. A causa di 3, i numeri che dovrebbero essere rimossi dall'elenco dai multipli sono: 6, 9, 12, 15, 18, 21 e 24. A causa di 5, i numeri che dovrebbero essere rimossi dai multipli sono: 10, 15, 20 e 25.

Per tutti i multipli, le rimozioni sono le seguenti:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 6, 9, 12, 15, 18, 21, 24

5: 10, 15, 20, 25

Per multipli, 6 vengono rimossi due volte (in teoria), 10 vengono rimossi due volte (in teoria), 12 vengono rimossi due volte (in teoria), 15 vengono rimossi due volte (in teoria), 20 vengono rimossi due volte (in teoria) e 24 vengono rimossi due volte (in teoria).

Tuttavia, se a causa di 3, la rimozione inizia da 3 x 3 = 9, quindi 6 viene rimossa una sola volta. Se a causa di 5, la rimozione inizia da 5 x 5 = 25, la rimozione di 10, 15 e 20 viene eseguita una volta ciascuna. Tuttavia, la rimozione di 12, 18 e 24 è ancora eseguita due volte per numero. Tuttavia, ci sarebbero alcuni vantaggi, poiché vengono omesse quattro operazioni ripetute di rimozione (per 6, 10, 15 e 20). Ciò migliora l'efficienza (complessità del tempo). Con ciò, le rimozioni saranno:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 9, 12, 15, 18, 21, 24

5: 25

I numeri 6, 10, 15 e 20 sono stati rimossi ciascuno una volta, anziché due volte. I numeri, 12, 18 e 24 sono stati rimossi due volte. A partire da ora, non si può fare nulla per rimuovere 12, 18 e 24 solo una volta.

Le situazioni per i numeri 36 e 37, o qualsiasi altro numero maggiore di 1, sono spiegate in modo simile.

Evitare la ridondanza

Rimuovendo semplicemente i multipli dei numeri primi da 2 al valore intero di √n, si ottiene l'insieme richiesto di numeri primi. L'efficienza può essere migliorata rimuovendo i multipli dei numeri primi, a partire dal quadrato del numero principale (i²) fino al valore intero di √n come precedentemente suggerito. Questo omette alcune operazioni di rimozione dei numeri. Quindi, riducendo il numero totale di operazioni. Il setaccio di Eratostene viene eseguito da questo secondo approccio.

Algoritmo del setaccio di Eratostene

L'algoritmo inizia creando un vettore indicizzato a base zero di lunghezza che è N+1. Ogni elemento di questo vettore viene inizializzato in booleano, vero, tranne il primo e il secondo elementi per l'indice 0 e l'indice 1 che sono inizializzati in falso. Per questo vettore, l'indice 2 corrisponde al numero (primo) 2; L'Indice 3 corrisponde al numero (Prime) 3; L'indice 4 corrisponde al numero 4; e così via. Poiché il vettore è indice basato su zero a, la lunghezza deve essere n+1 in modo che l'ultimo indice corrisponda a n.

Un numero di indice per questo elenco vettoriale che deve essere rimosso non viene rimosso di per sé: il valore del numero dell'indice viene fatto falso per indicare la rimozione. Cioè, all'elemento viene dato il valore falso. Quindi, se un numero (indice) deve essere rimosso dall'elenco (vettore) più di una volta, il valore per l'indice viene reso falso più di una volta.

Alla fine, gli indici per gli elementi del vettore i cui valori sono rimasti veri vengono letti come i numeri primi.

Prima di allora, i multipli di indici primi a partire dal quadrato dell'indice principale (i²) fino al valore intero di √n sono contrassegnati come falsi.

Coding C ++

Il programma in C ++ dovrebbe iniziare con quanto segue:

#includere
#includere
Utilizzo dello spazio dei nomi std;

Il setaccio della funzione Eratostene è il seguente:

vettore setaccio (int n)
vettore setaccio (n+1, vero);
setaccio [0] = false;
setaccio [1] = false;
int i = 2;
mentre (i * i <= n)
if (setaccio [i] == true) // se i è numero primo
int j = i * i;
mentre (j <= n) //marking multiples with false
setaccio [j] = false;
j = j + i; // incremento di multipli


i = i + 1; // incremento normale del ciclo esterno, di 1

restituzione setaccio;

Leggi i commenti del codice. Il nome della funzione è setaccio (). Il vettore restituito, dopo che tutti i multipli sono contrassegnati come falsi, è anche chiamato setaccio. Una funzione principale C ++ adatta per questo codice è:

int main (int argc, char ** argv)

vettore VTR = setaccio (37);
per (int i = 0; iif (vtr [i] == true)
cout << i << ";
cout << endl;
restituzione 0;

Con questo codice, l'output è il seguente:

2 3 5 7 11 13 13 17 19 23 29 31 37

La complessità temporale per questa funzione è O (n log log n).

Conclusione

L'algoritmo inizia creando un vettore indicizzato a base zero della lunghezza n+1. Ogni elemento di questo vettore viene inizializzato in booleano, vero, tranne il primo e il secondo elementi per l'indice 0 e l'indice 1 che sono inizializzati in falso. Per questo vettore, ogni indice è una serie di interessi. Poiché il vettore è basato su zero, la lunghezza deve essere n+1 in modo che l'ultimo indice sia n.

Il valore del numero che è l'indice è falso per indicare la rimozione. Cioè, all'elemento viene dato il valore falso.

Alla fine, gli indici per gli elementi del vettore i cui valori sono rimasti veri vengono letti come i numeri primi.

Prima di allora, i multipli di indici primi a partire dal quadrato dell'indice principale fino al valore intero di √n sono contrassegnati come falsi.