|
Trovandoci a parlare dei numeri primi, avrei bisogno di aiuto per capire il testo dell'esercizio (del libro dei fratelli Deitel che sto studiando e non di un corso) che recita così:
Un numero intero si dice primo se è divisibile soltanto per se stesso.
a) Scrivere una funzione che determina se il suo parametro è un numero primo
b) Utilizzare questa fuzione per scrivere un programma che determina e visualizza i numeri primi compresi tra 1 e 100.000. Quandi numeri avete bisogno di provare realmente prima di trovare tutti i numeri primi di questo intervallo?
c) Inizialmente penserete che non serve andare oltre n/2 per verificare se n è un numero primo, ma in realtà potete anche fermarvi alla sua radice quadrata. Perché? Riscrivere il programma ed eseguire le due versioni. Che miglioramento avete ottenuto sulle prestazioni?
Mi mette in crisi la c. Ho pensato di filtrare inizialmente i numeri escludendo quelli il cui modulo 2 restituiva 0 (divisibili per due) e mi trovo allineato.
Quando si fa riferimento alla radice quadrata di n l'unica cosa che mi è venuta in mente è che un numero che abbia una radice quadrata intera non sia un numero primo.
Il fatto è che se filtro per la seconda condizione (radice quadrata non intera) che ho pensato il programma degrada in termini di prestazioni rispetto alla prima soluzione (esclusione dei numeri divisibili per due). Nel testo dell'esercizio mi sembra chiaro che le prestazioni debbano aumentare e quindi credo di non aver capito esattamente cosa stia cercando di dirmi il libro nel punto c).
Grazie sempre per l'aiuto,
Unslee
|