Scomposizione in fattori primi
Scomponi un numero intero nei suoi fattori primi, elenca i suoi divisori e controlla se è primo.
Gira interamente nel tuo browser. Non viene caricato, registrato o salvato niente.
Scomposizione in primi
2^3 × 3^2 × 5
- È primo?
- no
- Fattori primi distinti
- 3
- Quanti divisori
- 24
- Divisori
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Ogni numero intero maggiore di 1 è un prodotto di primi, e ce n'è uno solo per lui: è il teorema fondamentale dell'aritmetica. Questo lo trova, e con lui tutto quello che ne discende: quanti divisori ha il numero e quali sono.
Come funziona
Divisione per tentativi, con una scorciatoia: tolti il 2 e il 3, tutti i primi rimasti stanno da una parte o dall'altra di un multiplo di sei, quindi i candidati avanzano di sei in sei invece che di due in due. Quello che sopravvive al setaccio è primo ed entra come ultimo fattore.
I divisori si costruiscono dalla scomposizione e non provando tutti i numeri fino a n. Un numero scritto come 2³ × 3² × 5 ha (3+1) × (2+1) × (1+1) = 24 divisori, e ognuno è una scelta di quanti di ciascun primo prendere, quindi elencarli non costa niente una volta nota la scomposizione.
Il tetto è mille miliardi. La divisione per tentativi tocca al massimo la radice quadrata del numero, che lì sono un milione di passaggi: veloce. Sopra, un numero che fosse il prodotto di due primi grandi lascerebbe la pagina a caricare per un minuto, quindi si rifiuta.
Esempi
| Caso | Dati inseriti | Risultato |
|---|---|---|
| Un numero con molti divisori | 360 | 2³ × 3² × 5: 24 divisori |
| Un primo | 97 | 97: primo, 2 divisori |
| Una potenza di due | 1024 | 2¹⁰: 11 divisori |
Domande frequenti
Perché comincia da 2 e non da 1?
Perché 1 non ha scomposizione in primi, e chiamarlo primo romperebbe l'unicità su cui poggia tutta la materia: se 1 fosse primo, 6 sarebbe 2 × 3, e 1 × 2 × 3, e 1 × 1 × 2 × 3, e non ci sarebbe più una sola risposta. Lo zero è ancora peggio: tutti i numeri lo dividono.
Quanti divisori ha un numero?
Aggiungi uno a ogni esponente della scomposizione e moltiplica. 360 è 2³ × 3² × 5, quindi 4 × 3 × 2 = 24. Un primo ne ha 2 — sé stesso e 1 — e un quadrato perfetto ne ha sempre un numero dispari, perché uno dei divisori è il compagno di sé stesso.
Perché c'è un tetto?
La divisione per tentativi è esatta e veloce finché non lo è più. Il caso peggiore è un prodotto di due primi vicini alla radice quadrata, e il limite qui è dove quel caso torna ancora dentro un caricamento di pagina. Un rifiuto ti dice cosa è successo; un timeout non ti dice niente.
È così che si rompono le chiavi di cifratura?
No, ed è proprio il punto. RSA poggia sulla difficoltà di scomporre un numero di qualche centinaio di cifre; la divisione per tentativi su uno di quelli durerebbe più dell'universo. I metodi che fanno meglio esistono e non si avvicinano nemmeno, ed è per questo che lo schema funziona.
Da sapere
- I divisori vengono elencati per intero fino a sessantaquattro; oltre viene mostrato solo il conteggio, perché una pagina di novecento numeri non è una cosa che legga qualcuno.
Tutti gli strumenti di Matematica