Calcolatore di scomposizione in fattori primi

Scomporre un numero in fattori primi

Ogni numero intero maggiore di 1 può essere scritto come prodotto di numeri primi in un solo modo, a meno dell'ordine dei fattori. È il teorema fondamentale dell'aritmetica, e la scomposizione in fattori primi di un numero è proprio quel prodotto unico. Per esempio, 360 = 2³ × 3² × 5. Questo calcolatore trova la scomposizione di qualsiasi numero intero fino a 9,007,199,254,740,991, cioè 2^53 − 1, il più grande intero che un browser può rappresentare in modo esatto. I risultati compaiono in forma esponenziale, in forma completamente espansa e come albero dei fattori.

I divisori, il loro numero e la loro somma

Una volta nota la scomposizione in fattori primi, molte altre proprietà seguono direttamente. Se un numero è uguale a p₁^a₁ × p₂^a₂ × …, il numero dei divisori positivi è (a₁ + 1)(a₂ + 1)…, perché ogni divisore sceglie per ciascun primo un esponente da 0 fino alla potenza piena. La somma dei divisori è il prodotto di (1 + p + p² + … + p^a) su tutti i primi. Per 360 si ottengono 4 × 3 × 2 = 24 divisori con somma 1170. Lo strumento elenca tutti i divisori in ordine crescente, il che aiuta a trovare i fattori comuni, semplificare le frazioni e verificare se un numero è perfetto, cioè se i suoi divisori diversi da sé stesso sommati danno il numero stesso.

Come funziona la scomposizione

I fattori primi piccoli vengono eliminati con la divisione per tentativi, usando una ruota che salta i multipli di 2 e 3. Ciò che rimane ha solo fattori primi grandi, quindi il calcolatore lo verifica con un test di Miller-Rabin deterministico e, se è composto, lo divide con l'algoritmo rho di Pollard (Pollard's rho) usando l'aritmetica esatta BigInt, per poi scomporlo ricorsivamente. In questo modo anche i prodotti di due primi dell'ordine delle decine di milioni vengono restituiti rapidamente, mentre la sola divisione per tentativi sarebbe lenta. L'albero dei fattori mostra un modo per arrivare ai primi togliendo a ogni passo il primo più piccolo.

La modalità batch ti permette di incollare un intero elenco di numeri e ricevere una tabella con la scomposizione e il numero di divisori di ciascuno, mentre le voci non valide vengono segnalate singolarmente senza interrompere l'elaborazione. Tutto viene calcolato nel tuo browser, quindi i numeri che inserisci non vengono mai caricati.