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, perché non è divisibile solo per 1 e per se stesso, ma anche per 2 e per 3.
Per usare il crivello di Eratostene, per prima cosa scrivi tutti i numeri da 2 fino al numero dato, incluso.
Poi segui questi passaggi:
- Trova il prossimo numero non marcato (saltando i numeri marcati).
Questo è un numero primo.
- Marca tutti i multipli di quel numero primo come non primi.
Ripeti i passaggi finché non hai esaminato tutti i numeri.
Alla fine, tutti i numeri non marcati sono primi.
Il crivello di Eratostene elimina i multipli di ogni numero primo usando l'addizione (sommando ripetutamente il numero primo) o la moltiplicazione (calcolando direttamente i suoi multipli), invece di verificare la divisibilità di ogni numero.
I test non verificano che tu abbia implementato l'algoritmo, ma solo che tu abbia trovato i numeri primi corretti.
Esempio
Diciamo che stai cercando i numeri primi minori o uguali a 10.
-
Scrivi 2, 3, 4, 5, 6, 7, 8, 9, 10, lasciandoli tutti non marcati.
2 3 4 5 6 7 8 9 10
-
2 non è marcato ed è quindi primo.
Marca 4, 6, 8 e 10 come «non primi».
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3 non è marcato ed è quindi primo.
Marca 6 e 9 come non primi (marcare 6 è opzionale, perché è già stato marcato).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4 è marcato come «non primo», quindi lo saltiamo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5 non è marcato ed è quindi primo.
Marca 10 come non primo (opzionale, perché è già stato marcato).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6 è marcato come «non primo», quindi lo saltiamo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7 non è marcato ed è quindi primo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8 è marcato come «non primo», quindi lo saltiamo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9 è marcato come «non primo», quindi lo saltiamo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10 è marcato come «non primo», quindi ci fermiamo perché non ci sono altri numeri da controllare.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Hai esaminato tutti i numeri e hai visto che 2, 3, 5 e 7 sono ancora non marcati: sono i numeri primi minori o uguali a 10.
