Calcolatore della scomposizione in fattori primi
Inserisci un numero intero. Lo scomponiamo in un prodotto di numeri primi, per esempio 360 = 2³ × 3² × 5.
Risultato
2³ × 3² × 5Scomposizione in fattori primi
- Numero di primi diversi
- 3
- 2 compare 3 volta/e
- 3 compare 2 volta/e
- 5 compare 1 volta/e
Dati inseriti
- Numero intero
- 360
Come si calcola
Dividiamo per 2 finché è possibile, poi per 3, 5, 7… (fino a 100.000).
Risultato
Scomposizione in fattori primi
- Numero di primi diversi
- 3
Come si calcola
- Dividiamo per 2 finché è possibile, poi per 3, 5, 7… (fino a 100.000).
- Se resta un fattore grande, cerchiamo un divisore con il metodo rho di Pollard.
- Ogni fattore viene controllato con il test di primalità di Miller–Rabin.
- Il tempo di calcolo è limitato: se non basta, lo strumento lo segnala senza bloccarsi.
Esempio
360 = 2 × 180 = 2 × 2 × 90 = … = 2³ × 3² × 5.
Da sapere
- Fino a 30 cifre. Un numero composto da due numeri primi molto grandi potrebbe essere rifiutato perché troppo grande.
- Oltre circa 25 cifre, un fattore primo è «probabile», non dimostrato.
Quando usarlo
- Scomponi un intero nei suoi fattori primi e nei relativi esponenti.
- Controlla se un numero è primo o quali fattori primi lo compongono.
Domande frequenti
Che cos’è la scomposizione in fattori primi?
È la scrittura di un numero come prodotto di numeri primi. Per esempio, 360 = 2³ × 3² × 5.
Che cosa significa «primo con altissima probabilità»?
Per fattori molto grandi il test di Miller–Rabin fornisce una verifica probabilistica, non una dimostrazione matematica definitiva.
Perché alcuni numeri grandi vengono rifiutati?
La ricerca dei fattori può richiedere troppo tempo, soprattutto se il numero contiene fattori primi molto grandi.