Introduzione
Hai comprato una grande scatola di componenti per computer a caso a un mercatino dell'usato.
Hai iniziato a mettere insieme i pezzi per costruire computer personalizzati.
Vuoi testare le prestazioni di diverse combinazioni di componenti, così decidi di creare il tuo programma di benchmark per vedere come si comportano i tuoi computer.
Scegli il famoso algoritmo «crivello di Eratostene», un algoritmo antico, ma che dovrebbe spingere i tuoi computer al limite.
Istruzioni
Il tuo compito è creare un programma che implementi l'algoritmo del crivello di Eratostene per trovare tutti i numeri primi minori o uguali a un numero dato.
Un numero primo è un numero maggiore di 1 che è divisibile solo per 1 e per se stesso.
Per esempio, 2, 3, 5, 7, 11 e 13 sono numeri primi.
Al contrario, 6 non è un numero primo, dato che è divisibile non solo per 1 e per se stesso, ma anche per 2 e per 3.
Per usare il crivello di Eratostene, per prima cosa crei un array con tutti i numeri compresi tra 2 e il numero dato.
Poi ripeti i passaggi seguenti:
- Trova il prossimo numero non marcato nell'array (saltando i numeri marcati).
Questo è un numero primo.
- Marca tutti i multipli di quel numero primo come non primi.
Continui a ripetere questi passaggi finché non hai esaminato tutti i numeri dell'array.
Alla fine, tutti i numeri non marcati sono primi.
I test non verificano che tu abbia implementato l'algoritmo, ma solo che tu abbia prodotto l'array corretto dei numeri primi.
Per verificare che tu stia implementando il crivello correttamente, un buon primo test è controllare che tu non usi operazioni di divisione o di resto.
Esempio
Supponi di dover trovare i numeri primi minori o uguali a 10.
- Elenca 2, 3, 4, 5, 6, 7, 8, 9, 10, lasciandoli tutti non marcati.
- 2 non è marcato ed è quindi un numero primo.
Marca 4, 6, 8 e 10 come «non primo».
- 3 non è marcato ed è quindi un numero primo.
Marca 6 e 9 come non primi (marcare 6 è facoltativo: è già stato marcato).
- 4 è marcato come «non primo», quindi lo saltiamo.
- 5 non è marcato ed è quindi un numero primo.
Marca 10 come non primo (facoltativo: è già stato marcato).
- 6 è marcato come «non primo», quindi lo saltiamo.
- 7 non è marcato ed è quindi un numero primo.
- 8 è marcato come «non primo», quindi lo saltiamo.
- 9 è marcato come «non primo», quindi lo saltiamo.
- 10 è marcato come «non primo», quindi ci fermiamo perché non ci sono più numeri da controllare.
Hai esaminato tutti i numeri e hai scoperto che 2, 3, 5 e 7 sono ancora non marcati, il che significa che sono i numeri primi minori o uguali a 10.
