Informatica I - Esercizi uso di array

Esercizio di laboratorio

Argomento: uso di array

Il Crivello di Eratostene è un noto algoritmo per la ricerca dei numeri primi minori di un certo valore massimo MAX, ed è così specificato:

• Si predispone un array di MAX valori booleani. Ogni elemento dell'array "rappresenta" il numero intero corrispondente al proprio indice nell'array.
• Se e solo se l'elemento è true, allora il numero corrispondente è stato eliminato dall'insieme dei numeri primi, cioè non è un numero primo.
• All'inizio si suppone che tutti i numeri siano primi; successivamente, si considera ciascun numero intero maggiore di uno, in ordine crescente, e si eliminano tutti i numeri che ne sono multipli, contrassegnandoli opportunamente nell'array.
• Al termine, i numeri rimasti (ovvero quelli i cui corrispondenti elementi nell'array valgono ancora false) sono tutti e soli i numeri primi cercati, non essendo multipli di alcun numero.

Scrivere un programma che realizza il Crivello di Eratostene per identificare i numeri primi minori di un valore (intero positivo) MAX fornito dall'utente attraverso l'ingresso standard. Verificare il corretto funzionamento del programma con:

• MAX = 1 (non viene visualizzato nessun numero, perché non esiste nessun numero primo minore di 1)
• MAX = 2 (viene visualizzato soltanto il numero 1)
• MAX = 3 (vengono visualizzati soltanto i numeri 1 e 2)
• MAX = 4 e MAX = 5 (vengono visualizzati soltanto i numeri 1, 2 e 3)
• MAX = 6 (vengono visualizzati soltanto i numeri 1, 2, 3 e 5)

Soluzione

Ecco una possibile soluzione. Osservate la costruzione dei due cicli annidati (for e while), che realizzano l'algoritmo descritto.

import java.util.Scanner;public class ErastoteneTester{ public static void main(String[] args){ Scanner in = new Scanner(System.in);int max = 0;while (max <= 0){ System.out.println("Inserisci valore max (intero positivo):");try{ max = Integer.parseInt(in.nextLine()); }catch (NumberFormatException e){ max = -1; }}boolean[] nonPrimes = new boolean[max]; //valori inizializzati a falsefor (int i = 2; i < max; i++){ int j = 2 * i;while (j < max){ nonPrimes[j] = true;j += i;}}System.out.println("Numeri primi minori di " + max + ":");for (int i = 1; i < max; i++)if (!nonPrimes[i]) System.out.println(i);}}