Fondamenti di Informatica - Ingegneria per l'Ambiente e il Territorio - A.A. 98/99

- Seconda esercitazione in laboratorio -

Problema (test di primalità)

"Dato un naturale n, stabilire se esso è primo oppure no"

Si propone di seguito il codice C di un programma che risolve il problema. Si invitano gli studenti a:

  1. Analizzare il programma per comprenderne la modalità di funzionamento.
  2. Scrivere il programma in un ambiente di sviluppo per il linguaggio C (ad es., TurboC).

#include <stdio.h>

main () {

int n, primo, divisore;

/* n e` il naturale da testare

primo e` una variabile che alla fine della esecuzione contiene uno fra i seguenti valori:

0 (n e` primo)

1 (n e` primo)

2 (errore, n e` negativo)

divisore contiene i vari divisori che si provano (2, 3, 4, ...) per stabilire se n e` primo

*/

printf("\n\n\nTest di primalita`. Benvenuti.\n");

printf("Digita il numero da testare: ");

scanf("%d", &n);

if (n <= 0)

primo = 2;

else {

primo = 1; /* assumiamo che n sia primo */

divisore = 2;

while (divisore < n) {

if (n % divisore == 0)

primo = 0; /* e` stato trovato un divisore */

divisore = divisore + 1;

}

}

if (primo == 0)

printf("Il numero %d non e` primo.", n);

else if (primo == 1)

printf("Il numero %d e` primo.", n);

else /* (primo == 2) */

printf("Errore: hai immesso un numero negativo.");

printf(" Arrivederci.\n");

}

Attività di raffinamento

Con riferimento al programma di cui sopra, sono evidenti alcuni limiti dello stesso:

  1. In caso di numero non primo, il programma continua (inutilmente) a lavorare anche se trova subito un divisore.
  2. Il test utilizzato nel ciclo while usa un valore limite (n) inutilmente elevato (per verificare se un naturale m è primo basta cercare un divisore nell'intervallo ).
  3. Se il numero non è primo il programma non ci dà informazione alcuna sui suoi divisori.

Ciò premesso, si invitano gli studenti a modificare il programma in modo da ovviare ai limiti descritti. In particolare, scrivere un programma per il test di primalità che termini non appena la risposta al test sia "certa" e restituisca, in caso di numero non primo, il più piccolo divisore del numero.