Homework (compito per casa) 2

Crivello di Eratostene

Vedi anche: DomandeHomework204, SoluzioneHomework204, RisultatiHomework204

---

---

Descrizione

I numeri primi si definiscono in matematica come quei numeri naturali che sono divisibili solo per 1 e per se stessi. Esiste un antichissimo metodo (forse uno dei primi algoritmi di cui si abbia conoscenza) per generare tutti i numeri primi da 1 ad N, noto come Crivello di Eratostene, che risale al III secolo avanti Cristo: si scrivono tutti i numeri naturali da uno a N. Si comincia da 2 e si cancellano tutti i suoi multipli (4,6,8,10, ...). Si prende il prossimo numero non cancellato, il 3, e si cancellano tutti i suoi multipli (6,9,12,15, ...). A questo punto il primo numero non cancellato è il 5 e si cancellano i suoi multipli, e cosi' via. Alla fine, seguendo questo procedimento, i numeri non cancellati sono tutti i numeri primi tra 1 e N. (quando ci si può fermare in realtà?).

Voi dovrete semplicemente scrivere un programma che:

• genera tutti i numeri primi da 1 a 10000 [SUGG: usare un array, inizializzare tutti i suoi elementi a 1; poi applicare l'algortimo di Eratostene, dove cancellare il numero i, significa porre a 0 l'iesimo elemento dell'array];
• accetta in input un'intero positivo e si comporta nel seguente modo:
• se l'intero è 0 si ferma;
• se l'intero è compreso tra 1 e 10000, stampa 1 se il numero è primo, 0 altrimenti e poi aspetta in input un nuovo numero;
• se l'intero è negativo o strettamente maggiore di 10000, stampa -1 e poi chiede in input un nuovo numero.

IMPORTANTE

• non far produrre al programma altri output oltre a quelli richiesti.
• inserire l'istruzione:

Ecco una tabella dei numeri primi da 1 a 100 che potrebbe esservi utile per testare il programma:

 
 1    2    3    5    7   11   13   17   19   23   29   31   37   
41   43   47   53   59   61   67   71   73   79   83   89   97  

Input

Il vostro programma riceve in input una sequenza di numeri interi chiusa da uno zero;

Output

Il vostro programma deve stampare 1 se il numero inserito è positivo e primo, 0 se è positivo e composto, -1 se il numero inserito è negativo o strettamente maggiore di 10000 e continuare a chiedere un nuovo numero finchè non viene inserito uno 0.

Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente!

Come compilare ed eseguire il programma

• usate un editor per scrivere il testo del programma e salvatelo in formato testo semplice in un file con l'estensione .c (ad esempio di nome trexpuno.c)
  • NON usate Word, Openoffice, Kword, Abiword che introducono caratteri strani
• compilate (e contemporaneamente linkate) il programma con il comando

gcc -g -o eratostene eratostene.c

• eseguite il programma scrivendo

./eratostene

Come consegnare il programma

• Avete tempo fino a Martedì 30 Novembre alle ore 23.59 (ora sono le 19:35 del 23).
• Consegnate il testo del programma sorgente C da voi scritto. Io lo compilerò e testerò.
• Usate esclusivamente la pagina di consegna. Non verranno accettate spedizioni via email.

• Set ALLOWTOPICCHANGE = DocentiProg1Group

-- IvanoSalvo - 18 Nov 2004