Numero primo? (scuola media)

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

Versione di Scratch utilizzata

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

Cosa richiede l'esercizio

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

La velocità di calcolo del Template:Vk 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 $36$
Video per chi non ama leggere: Template:YouTube
Proviamo: $36 : 2 = 18$ quindi $2$ è un divisore di $36$ , scopriamo così che anche $18$ lo è, quindi, per ora,
$D_{36} = {1, 2, . . . 18, 36}$
Se stessimo facendo il nostro controllo potremmo già fermare la ricerca:
« $36$ non è un numero primo.»
Continuiamo però per comprendere quando potremo interromperla avendo trovato tutti i divisori.
$36 : 3 = 12$ quindi $3$ e $12$ sono divisori di $36$ , e lo stesso
$36 : 4 = 9$ quindi $4$ e $9$ sono divisori di $36$ ,
notiamo che al crescere dei divisori i quozienti diminuiscono, non proviamo a dividere per $5$ , invece
$36 : 6 = 6$ quindi $6$ è un divisore di $36$ , 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 $9, 12 o 18$ Quindi tutti i divisori di $36$ sono
$D_{36} = {1, 2, 3, 4, 6, 9, 12, 18, 36}$
dove i primi $2, 3, 4, 6$ sono stati trovati come divisori, mentre gli altri $6, 9, 12, 18$ 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 $73$

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

$73 : 2 = 36, 5$ non è un divisore e notiamo che $2 < 36, 5$ ,

$73 : 3 = 24, 33$ non è un divisore e $3 < 24, 33$ ,

$73 : 4 = 18, 25$ non è un divisore e $4 < 18, 25$ ,
ricordiamo che se un numero non è divisibile per $2$ non lo è nemmeno per $4$ , il pc questa operazione le prova lo stesso, ma in un tentativo non digitale questa prova viene omessa,

$73 : 5 = 14, 6$ non è un divisore e notiamo che $5 < 14, 6$ ,

$73 : 6 = 12, 16$ non è un divisore e $6 < 12, 16$
, vale lo stesso di quello scritto per $4$ ,

$73 : 7 = 10, 42$ non è un divisore e notiamo che $7 < 10, 42$ ,

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

$73 : 8 = 9, 125$ non è un divisore e $8 < 9, 125$ ,

$73 : 9 = 8, 11$ non è un divisore e notiamo che $9$ è il primo divisore più grande del quoziente infatti $9 > 8, 11$ ,

quindi, per ora eventuali altri divisori più grandi di $9$ dovrebbero produrre quozienti più piccoli di $9$ ma come abbiamo appena controllato non ce ne sono.
Le prove sono finite e possiamo concludere che $73$ è 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 $7$ è $11$ e il risultato è

$73 : 11 = 6, 64$ non è un divisore e come per $9$ , verifichiamo che il divisore è più grande del quoziente infatti $11 > 6, 64$
.

Variabili

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: , ,

Input e Valori iniziali

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

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

Il ciclo repeat until

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
		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.
		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 $2$ in questo controllo dobbiamo anche inserire che il numero sia diverso dal divisore.

Numeri non primi fermare il ciclo repeat

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
		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).
		Con questa condizione si evita che il programma risponda in modo scorretto se riceve in input il numero $2$ , 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.
		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 $2$ , che ci serve solo per evitare l'errore di questo caso particolare.

Codice completo test numero primo

Sprite	Blocchi codice	Istruzioni
		Codice completo del progetto.

Schema progetto da montare

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

Note

Bibliografia

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

Numero primo? (scuola media)

Indice