trova divisori

Page 4 of 6

Dobbiamo verificare se k è effettivamente un divisore di N. A tal scopo calcoliamo il resto della divisione (funzione modulo!) fra n e k. Se il resto è zero allora k è un divisore di N

k=2
mentre(k <= √N){
     resto= N modulo k
    ...
    k=k + 1
}

C'è una piccola complicazione. Non ci basta sapere se k è un divisore di N ma vogliamo sapere quante volte k divide N. Facciamo un esempio:

se N=80 la sua scomposizione é 2⁴ * 5 perciò 2 divide 80 quattro volte. Perciò abbiamo bisogno di un contatore che chiameremo exp (valore iniziale 0) e di una ulteriore struttura iterativa che calcoli quante volte k divide N.


k=2
mentre(k <= √N){
    resto = N modulo k
    exp=0
    mentre (resto=0){ 
        exp=exp+1
        N=N/k
        resto=N modulo k // calcoliamo il NUOVO n modulo k ( N è stato modificato)
    }
...
k=k + 1
}

Quando usciamo dal ciclo suddetto exp conterrà il valore dell'esponente che però potrà essere anche uguale a zero. Non ci resta altro che visualizzare il valore del divisore k e di exp, ma solo se exp è diverso da zero. Quando usciamo dal ciclo più esterno se N è diverso da 1, lo mostriamo perché è l'ultimo fattore della scomposizione.

Scomposizione in fattori primi - trova divisori