# Scomposizione in fattori primi (scuola media)
## Scomposizione in fattori primi (scuola media)

Trovare i fattori primi di un numero. 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, il calcolatore restituisce l'elenco dei fattori primi, compresi quelli ripetuti.

## Come funziona

La velocità di calcolo del PC$^{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 calcolare solo dopo aver individuato tutti i fattori. Per individuare tutti i fattori non faremo altro che fare tentativi ripetuti. Dato il numero iniziale, una parte del programma si occuperà di provare a dividerlo per tutti i numeri. Se il resto è diverso da zero il divisore viene incrementato di uno e si riprova.
I tentativi si interrompono per due motivi:
* se viene individuato un fattore, allora il quoziente ottenuto prende il posto del numero da scomporre e si ricomincia, avendo l'accortezza di usare come prima prova una seconda volta il fattore appena individuato,
* il numero del quale si cercano i divisori è primo, cosa che si comprende dal fatto che il fattore, divisore, diventa più grande del quoziente e quindi non ci sono più possibili divisori.
In questo modo vengono individuati solo i fattori primi poiché una volta diviso il numero iniziale per tutte le eventuali potenze di un fattore primo il quoziente che ne risulta non è più divisibile per quel numero primo né per un qualsiasi suo multiplo, oppure è primo già il numero iniziale.

## Esempio di funzionamento della scomposizione con scratch

Scomponiamo il numero 36:
* $36:2=18$ quindi $36$ non è un numero primo, $2$ è un fattore di $36$
** prendiamo $2$ e lo mettiamo tra i fattori primi $36=2\ \cdot {\underbrace {18} _{\text{non primo}}}=2\ \cdot {\underbrace {...} _{\text{fattori primi}}}$
** sostituiamo $36$ con $18$ e ricominciamo.
* $18:2=9$ quindi $18$ non è un numero primo, $2$ è un fattore di $36$
** prendiamo $2$ e lo mettiamo tra i fattori primi $36=2^{2}\cdot ...$
** sostituiamo $18$ con $9$ e ricominciamo.
* $9:2=numero\ con\ la\ virgola$ quindi $2$ non è un divisore di $9$: è un fattore di $36$
** cerchiamo il numero primo successivo $3$ e ricominciamo.
* $9:3=3$ quindi $9$ non è un numero primo, $3$ è un fattore di $36$
** prendiamo $3$ e lo mettiamo tra i fattori primi $36=2^{2}\cdot 3\cdot ...$
** sostituiamo $3$ con $3$ e ricominciamo.
* $3:3=1$, il divisore è diventato più grande del quoziente $3>1$, mettiamo $3$ tra i fattori di $36$: $36=2^{2}\cdot 3^{2}$.
Abbiamo finto.

## Variabili e lista

Cominciamo con preparare le variabili necessarie (input) al funzionamento: Numero e NumeroIniziale, la variabile NumeroIniziale ci serve per archiviare il numero da scomporre, Divisore e Quoziente. L'output finale sarà una lista di fattori dobbiamo quindi predisporre anche una lista: Fattori. Per creare una variabile si deve andare nel menù variabile e Crea una variabile, in inglese Make a variable, nello stesso menù si trova anche Crea una lista, o il corrispondente Make a list.
| Istruzioni | Immagini |
| Andando nel menù variabile creiamo 4 variabili: Numero, NumeroIniziale, Divisore, Quoziente | Eccole: , , , , |
| Creiamo la lista Fattori: che verrà compilata mano a mano che si troveranno i fattori primi | |

## Input e Valori iniziali

Il nostro programma comincia clikkando sulla bandiera verde. Per prima cosa poniamo il divisore uguale a $1$ e poi il Gatto ci chiederà quale numero vogliamo testare.
* Istruzioni
* Inizio del programma
* Svuotiamo la lista dei fattori
* Poniamo il divisore uguale a $1$
* Il gatto ci pone la domanda Numero? e assegna la risposta a tutte e due le variabili Numero e NumeroIniziale
* Il Quoziente, il primo Quoziente, viene posto uguale al Numero, altro non è che il risultato della prima divisione con Divisore $1$

## Il ciclo repeat until

La ricerca dei fattori primi, i divisori con resto zero, avverrà grazie ad un ciclo repeat. Il ciclo si ripete fino a che il divisore, incrementato ad ogni passaggio, non diventerà più grande del quoziente.
* 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.
* Ad ogni passaggio, nell'ipotesi che il resto sia dverso da zero il divisore viene incrementato di 1. Ed il quoziente viene posto come risultato della divisione, ottenendo così che il divisore aumenta e il quoziente diminuisce. Se non si trovassero divisori, cioè se non si verificasse mai la condizione resto uguale a zero (in inglese numero mod divisore = 0) il ciclo repeat si fermerebbe al primo divisore maggiore del quoziente restituendo il fatto che il numero iniziale è primo.
* Condizioni per l'interruzione del ciclo, avviene se individuato un fattore, cioè un divisore che dà resto 0.
* Trovato il divisore-fattore primo:
* lo si aggiunge alla lista dei Fattori,
* si diminuisce di 1 il divisore in modo che alla ripresa del ciclo venga riprovato un'altra volta il fattore individuato,
* si sostituisce il numero con il quoziente appena ottenuto e si ricomincia il ciclo con il numero portato al quoziente
* Questo è il blocco che aggiunge il divisore-fattore alla lista dei fattori primi
* Questa istruzione toglie 1 al divisore in modo che alla ripresa del ciclo venga provato un'altra volta il divisore del ciclo precedente, in modo da individuare quei fattori primi presenti due o più volte.
* Questa istruzione toglie 1 al divisore in modo che alla ripresa del ciclo venga provato un'altra volta il divisore del ciclo precedente, in modo da individuare quei fattori primi presenti due o più volte.
* Il quoziente, risultato della divisione tra il numero e il divisore-fattore trovato, prende il posto del numero e si ricomincia a cercare altri divisore-fattori primi.

## Output: i fattori primi

Un primo output viene fornito dalla compilazione della lista dei fattori che si conclude una volta che sono stati individuati tutti, condizione che si verifica quando l'ultimo quoziente diventa più piccolo del divisore.
| Sprite | Blocchi codice | Istruzioni |
| | | L'ultimo numero che si prova a dividere deve essere aggiunto alla lista come fattore primo, eventualmente come unico elemento, nel caso il numero che si è provato a scomporre fosse primo. |
| | | Dopo aver aggiunto il numero finale, l'ultimo che si è provato a dividere si incontra una istruzione condizionale (if, se) che conclude la scomposizione. Se il numero ed il mumero iniziale sono uguali il numero da scomporre è primo, e quindi nella lista comparirà solo lui, il numero si aggiunge agli altri fattori della scomposizione elencati nella lista. |

## Codice completo scomposizione in fattori primi

| Sprite | Blocchi codice | Istruzioni |
| | | Codice completo del progetto. |

## Stage del progetto

| Stage | Istruzioni |
| | Come appare il progetto sullo stage, sulla destra è visibile la lista che a scomposizione completata si riempie di fattori |

## Schema progetto da montare

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