Un possibile miglioramento è il seguente: puoi fermarti alla radice quadrata di N. Infatti, quando trovi un divisore, ne trovi in realtà due: per avere l'altro ti basta fare la divisione vera e propria. Prendiamo come esempio 14, e diciamo che la sua radice quadrata è 4 (arrotondamento per eccesso). Allora partiamo:
- 1 è un divisore, e questo ti dà anche il divisore 14/1=14
- 2 è un divisore, e questo ti dà anche 14/2=7
- 3 non è un divisore, quindi niente
- 4 non è un divisore
Stop: abbiamo raggiunto la radice quadrata e ci fermiamo. In conclusione i divisori sono 1, 2, 7 e 14.
Sperando di non aver detto stupidaggini, questo metodo ti aiuta a ridurre un po' i calcoli. In ogni caso tieni presente che fattorizzare un numero non è in generale un'operazione complessa, ammesso ovviamente di non pescare alcuni numeri particolari (cfr. algoritmo di crittografia RSA). Un'idea molto parziale è la seguente. Provi a dividere il numero per 2: se è un divisore, continui a dividere per 2 finché è possibile, aumentando un contatore che rappresenterà poi l'esponente. Quindi passi a 3, quindi a 4 (questo si può saltare perché già "compreso" nel 2 che hai provato prima), quindi 5, ecc. Esempio pratico: prendiamo il numero 36.
36 è divisibile per 2: aumento di uno il contatore associato al fattore 2
18 è divisibile per 2: aumento di uno il contatore associato al fattore 2
9 non è divisibile per 2, quindi con il 2 ho finito. Il contatore vale 2, quindi ottengo 2^2 e passo al 3
9 è divisibile per 3: aumento di uno il contatore associato a 3
3 è divisibile per 3: aumento di uno il contatore associato a 3
1 è la condizione di terminazione.
In conclusione ottieni 2^2 * 3^2, che è la scomposizione desiderata.