Vai al contenuto

Numero primo? (scuola media)

Da Wikiversità, l'apprendimento libero.
lezione
lezione
Numero primo? (scuola media)
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Informatica per la scuola media 1
Avanzamento Avanzamento: lezione completa al 100%

Numero primo? (scuola media)

[modifica]

Scoprire se un numero è primo oppure composto. Si può fruire di questo tutorial in forma di mappa mentale su wiki2map

Versione di Scratch utilizzata

[modifica]

La versione di scratch usata in questo progetto è scratch 3.0 online.


Cosa richiede l'esercizio

[modifica]

Fornito un numero numero in input, rispondendo alla richiesta del gatto, attraverso un numero di prove adeguato scoprire se il numero è primo oppure non lo è, e, ovviamente, ottenere in output il responso.

Come controllare se un numero è primo

[modifica]

La velocità di calcolo del PCVK permette di eseguire molti calcoli in poco tempo, questa capacità di lavoro ci permette di affrontare il problema per tentativi, avendo però l'accortezza di produrre i nostri tentativi in modo ordinato, cosa che ci permetterà di essere esaustivi, cioè di smettere di provare nel momento in cui si ha la certezza di aver provato, ed eventualmente trovato, tutti i divisori possibili.
Per chiarezza un procediamo con un esempio commentandolo, considerando dapprima come si possono trovare tutti i divisori di un numero, il nostro controllo necessita di meno operazioni e si fermerà eventualmente al primo divisore trovato.

Troviamo i divisori di
Video per chi non ama leggere: Filmato audio Matteo Ruffoni, Trovare divisori per tentativi 2, su YouTube, 16 gennaio 2020.
Proviamo: quindi è un divisore di , scopriamo così che anche lo è, quindi, per ora,

Se stessimo facendo il nostro controllo potremmo già fermare la ricerca:
« non è un numero primo.»
Continuiamo però per comprendere quando potremo interromperla avendo trovato tutti i divisori.
quindi e sono divisori di , e lo stesso
quindi e sono divisori di ,
notiamo che al crescere dei divisori i quozienti diminuiscono, non proviamo a dividere per , invece
quindi è un divisore di , ed è l'ultimo.
Infatti il divisore è uguale al quoziente, i prossimi divisori saranno tutti più grandi dei rispettivi quozienti, e quali mai potrebbero essere se non i quozienti già trovati Quindi tutti i divisori di sono

dove i primi sono stati trovati come divisori, mentre gli altri sono stati trovati come quozienti, ma sono a loro volta divisori.

Per maggior chiarezza proviamo ora con un numero che sappiamo già essere primo.

Testiamo il numero

Facciamo alcune prove come se fossimo un PC, quindi proviamo tutti i casi:

non è un divisore e notiamo che ,

non è un divisore e ,

non è un divisore e ,
ricordiamo che se un numero non è divisibile per non lo è nemmeno per , il pc questa operazione le prova lo stesso, ma in un tentativo non digitale questa prova viene omessa,

non è un divisore e notiamo che ,

non è un divisore e
, vale lo stesso di quello scritto per ,

non è un divisore e notiamo che ,

Il pc prosegue le sue prove con e anche se già si sa che nessno dei due è un divisore di

non è un divisore e ,

non è un divisore e notiamo che è il primo divisore più grande del quoziente infatti ,

quindi, per ora eventuali altri divisori più grandi di dovrebbero produrre quozienti più piccoli di ma come abbiamo appena controllato non ce ne sono.
Le prove sono finite e possiamo concludere che è primo.
In un eventuale test condotto senza PC molte prove possono essere omesse, così come evidenziato, tenendo conto dei criteri di divisibilità e del fatto che se un numero non è divisibile per un numero non lo sarà nemmeno per un suo multiplo. In un test manuale il divisore da provare dopo il è e il risultato è

non è un divisore e come per , verifichiamo che il divisore è più grande del quoziente infatti
.

Variabili

[modifica]

Cominciamo con preparare le variabili necessarie (input) al funzionamento Numero, Divisore e Quoziente. L'output ci verrà fornito con una frase.

Istruzioni Immagini
Creiamo 3 variabili:

Numero, Divisore, Quoziente

Eccole:

scratch block, VariabileDivisore, VariabileQuoziente


Input e Valori iniziali

[modifica]

Il nostro test comincerà clikkando sulla bandiera verde.
Per prima cosa poniamo il divisore uguale a e poi il Gatto ci chiederà quale numero vogliamo testare.

Sprite Blocchi codice Istruzioni
SetDivisoreTo Poniamo il divisore uguale a
AskNumeroSetNumero Il gatto ci pone la domanda Numero? e assegna la risposta alla variabile.
SetQuozienteToNumero Il Quoziente, il primo Quoziente, che altro non è che il risultato della prima divisione con Divisore


Il ciclo repeat until

[modifica]

Questo ciclo si ripeterà, a meno si non trovare prima un divisore, fino ad esaurire tutti i possibili divisori del numero, cosa che si raggiunge appena il divisore diventa maggiore del quoziente. Ad ogni passaggio viene incrementato il divisore.

Sprite Blocchi codice Istruzioni
RepeatUntilDivisoreMaggioreQuoziente Il ciclo con la condizione, funzionerà fino a che il divisore non diventerà maggiore del quoziente, se il ciclo va fino in fondo continuando fino a che il divisore supera il quoziente condizione che lo termina allora, di conseguenza, il numero è primo.
RepeatUntilDivisoreMaggioreQuozienteIfRestoZeroStop Il ciclo con le istruzioni:
  • incrementa il divisore
  • porta il quoziente al risultato del numero diviso il divisore
  • controlla che il resto non sia zero, nel qual caso interrompi il ciclo, il numero non è primo. Per evitare un errore che si verifica con il numero in questo controllo dobbiamo anche inserire che il numero sia diverso dal divisore.

Numeri non primi fermare il ciclo repeat

[modifica]

Se un numero è primo il ciclo repeat termina quando il divisore diventa maggiore del quoziente e il Gatto ci comunica che il numero è primo.

Dobbiamo però prevedere di interrompere il ciclo nel momento in cui venga trovato un divisore cosa che ci viene rivelata dalla comparsa di un divisore del numero, comparsa che ci viene rivelata dal fatto che il resto della divisione tra numero e divisore diventa uguale a zero.

Sprite Blocchi codice Istruzioni
scratch block Se il resto della divisione di (Numero) diviso (Divisore) = (0), in inglese molto più semplicemente mod, resto nullo significa che abbiamo trovato un divisore e quindi il numero non è primo, il ciclo può essere interrotto anche se non ha raggiunto la condizione (Divisore) > (Quoziente).
scratch block Con questa condizione si evita che il programma risponda in modo scorretto se riceve in input il numero , per provare la sua utilità basta levarlo dal codice e notare come questo causa l'errore. Si può notare come per costruire la condizione diverso si deve usare il costrutto not + uguale.
scratch block Combinando le condizioni con la congiunzione and richiediamo che entrambe siano vere per interrompere il ciclo: che il resto sia zero, quella che funzionerà sempre, e che non stiamo testando il numero , che ci serve solo per evitare l'errore di questo caso particolare.

Codice completo test numero primo

[modifica]
Sprite Blocchi codice Istruzioni
NumeroPrimoCode Codice completo del progetto.

Schema progetto da montare

[modifica]

A questo link https://scratch.mit.edu/projects/360377083/ si trova il progetto scratch smontato va remixato e montato nella sequenza corretta.

Note

[modifica]

Bibliografia

[modifica]
  • Guida all’uso di Scratch Versione Studenti; Alberto Barbero, Marco Marchisotti, Alberto Davì; Associazione Dschola, Iniziativa realizzata nell’ambito del progetto Diderot della Fondazione CRT, 2014

Collegamenti esterni

[modifica]