Tags:
create new tag
view all tags

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! frown

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 09:49 del 25).
  • 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.

-- IvanoSalvo - 18 Nov 2004

Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r5 - 2004-11-23 - IvanoSalvo






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback