Calcolatrice dei fattori primi

360 = 2^3 * 3^2 * 5; Omega(360) = 3 + 2 + 1 = 6; d(360) = (3+1) * (2+1) * (1+1) = 24

n

Il numero che viene spezzato — un numero intero da 1 a 1.000.000. L'intervallo è quello che il modulo di teoria dei numeri usa ovunque, quindi coincide esattamente con la pagina dei fattori e chi passa dall'una all'altra ritrova gli stessi bordi. I decimali vengono rifiutati invece di essere arrotondati, e 0 e i numeri negativi vengono rifiutati perché la scomposizione in fattori primi è un'affermazione sui numeri interi positivi

p

Un fattore primo — un numero primo che divide n esattamente. La pagina li trova per divisione per tentativi in ordine crescente, quindi il più piccolo esce sempre per primo e la scomposizione stampata va sempre dal primo più piccolo al più grande. Per 360 i primi sono 2, 3 e 5, e nessun altro primo lo divide

e

L'esponente su un primo — quante volte quel primo compare nel prodotto. 360 è 2 × 2 × 2 × 3 × 3 × 5, quindi il 2 compare tre volte e il 3 due volte. Un primo che compare una volta sola viene stampato senza alcun esponente: il 5 di 360 si scrive come un semplice 5 e non come 5^1, che è la convenzione usuale e tiene leggibili le scomposizioni corte

2^3 * 3^2 * 5

La scomposizione di 360 come viene stampata, e l'ingresso predefinito. L'accento circonflesso sta per l'esponente e l'asterisco per la moltiplicazione, così il tutto sopravvive all'essere copiato in un campo di testo semplice o in una casella di ricerca. Esiste esattamente un'espressione di questo tipo per ogni numero intero maggiore di 1, ed è ciò che la rende degna di essere stampata: 360 non si può scrivere anche come un altro prodotto di primi

Omega(360) = 3 + 2 + 1 = 6

Il numero di fattori primi contando le ripetizioni: tre 2, due 3 e un 5 fanno sei. È il conteggio che sorprende, perché 360 dà l'impressione di essere costruito da tre primi invece che da sei. La ricetta è sommare gli esponenti invece di contare i primi distinti, e le due risposte differiscono ogni volta che un esponente supera 1

d(360) = (3+1) * (2+1) * (1+1) = 24

Il numero di divisori positivi, ricavato dagli stessi esponenti sommando uno a ciascuno e moltiplicando. L'elenco è 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 e 360 — ventiquattro. È una domanda diversa da quella qui sopra: conta i numeri che dividono 360, non i primi che lo costruiscono

La scomposizione è quello che ti serve quando la domanda riguarda la struttura moltiplicativa di un numero invece della sua grandezza. Semplificare una frazione o una radice è il caso di ogni giorno: la radice quadrata di 72 si semplifica in 6√2 perché 72 = 2³ × 3², e l'esponente di ciascun primo ti dice quanto di quel primo può uscire da sotto il segno di radice — è la stessa scomposizione che legge la pagina dei radicali. Trovare il massimo comun divisore o il minimo comune multiplo di due numeri è ancora questo, fatto una volta per numero: i primi in comune presi con l'esponente più piccolo danno il primo, e tutti i primi presi con l'esponente più grande danno il secondo. Le domande di divisibilità si risolvono allo stesso modo, dato che un numero ne divide un altro esattamente quando i suoi primi e i suoi esponenti sono tutti disponibili nell'altro. In teoria dei numeri la scomposizione stabilisce se un numero è primo, quanti divisori ha, se è un quadrato perfetto (tutti gli esponenti pari) e se è un cubo perfetto. Vale la pena conoscere anche i limiti del metodo: la divisione per tentativi è veloce su un milione e disperata su un numero di cento cifre, e quel divario fra facile e difficile è esattamente ciò su cui è costruita la crittografia a chiave pubblica. Quando la domanda è quali numeri dividono il tuo invece di quali primi lo costruiscono, la pagina dei fattori li elenca; quando è se il numero è primo o no, la pagina dei numeri primi risponde direttamente.

1. Il caso predefinito: 360

   1. 360 è pari, quindi dividi per 2: 360 / 2 = 180, poi 180 / 2 = 90, poi 90 / 2 = 45 — tre volte in tutto
   2. 45 è dispari; il primo successivo è 3, e 45 / 3 = 15, poi 15 / 3 = 5 — due volte
   3. 5 è primo, quindi la scomposizione è 2 × 2 × 2 × 3 × 3 × 5, scritta 2^3 * 3^2 * 5
   4. Conta i fattori primi con le ripetizioni: 3 + 2 + 1 = 6
   5. Conta i divisori dagli esponenti: (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24

   L'ingresso predefinito, e quello che mostra perché i due conteggi vengono stampati affatto. Sei e ventiquattro stanno uno accanto all'altro e chi si aspetta che coincidano penserà che uno dei due sia rotto. Non lo sono: sei è da quanti pezzi primi il numero è fatto tenendo ogni ripetizione, e ventiquattro è quanti numeri lo dividono. Il divario fra i due viene dagli esponenti: ogni ripetizione di un primo moltiplica il numero di divisori senza aggiungere granché al conteggio dei pezzi. Verifica l'uno o l'altro a mano e l'aritmetica è breve; verificali entrambi e ti ricorderai quale è quale.

2. Il caso piccolo che mostra il divario: 12

   1. 12 / 2 = 6, e 6 / 2 = 3, quindi il 2 compare due volte
   2. 3 è primo, quindi la scomposizione è 2^2 * 3
   3. Conta i fattori primi con le ripetizioni: 2 + 1 = 3, cioè 2, 2 e 3
   4. Elenca i divisori: 1, 2, 3, 4, 6, 12 — sei
   5. Verifica con la ricetta: (2 + 1) × (1 + 1) = 3 × 2 = 6, che corrisponde all'elenco

   L'esempio piccolo più chiaro della confusione attorno a cui è costruita questa pagina, perché entrambi i conteggi sono abbastanza piccoli da verificare a mano in pochi secondi. Dodici è fatto di tre primi — 2, 2 e 3 — e sei numeri lo dividono. Leggere il risultato come 3 divisori oppure come 6 fattori primi suona plausibile in entrambi i casi ed è sbagliato in entrambi. L'elenco dei divisori mostra anche l'accoppiamento che rende sei un conteggio pari: 1 con 12, 2 con 6, 3 con 4. Dodici non è un quadrato perfetto, quindi nessun divisore si accoppia con se stesso, ed è per questo che il conteggio è pari.

3. Il caso scomodo: 1

   1. 1 non è divisibile per nessun primo: diviso per 2, per 3, per 5 o per qualsiasi altro lascia una frazione
   2. Quindi non ci sono fattori primi, e il loro conteggio è 0
   3. L'unico numero positivo che divide 1 è 1 stesso, quindi il numero di divisori è 1
   4. La scomposizione si stampa come la singola cifra 1 invece che come un campo vuoto

   Il caso che va deciso invece che derivato, e la decisione è stampare 1. Lasciare vuota la scomposizione si leggerebbe come un calcolo fallito, che è l'unica cosa che un pannello dei risultati non deve mai sembrare. I due conteggi poi cadono onestamente: nessun primo e un divisore. Uno non è né primo né composto — è l'identità moltiplicativa, il numero che non cambia niente quando ci moltiplichi — e la pagina non finge il contrario. Viene accettato invece che rifiutato perché l'intervallo di ingresso parte da 1, e un intervallo che esclude il proprio valore inferiore sarebbe una cosa più strana da spiegare.

L'ingresso deve essere un numero intero da 1 a 1.000.000. Lo zero viene rifiutato: ogni primo divide lo zero, quindi il prodotto dovrebbe essere infinito. I numeri negativi vengono rifiutati per un motivo affine — i primi li dividono comunque, ma il segno va portato a parte e l'enunciato di unicità riguarda i numeri positivi. I decimali vengono rifiutati invece di essere arrotondati, dato che arrotondare risponderebbe in silenzio a una domanda su un altro numero. Il tetto di un milione viene dal modulo di teoria dei numeri condiviso ed è una questione di costo più che di correttezza: la divisione per tentativi su ogni primo fino alla radice quadrata è veloce su un milione e disperata su un numero di venti cifre. È un confine autentico del metodo, ed è lo stesso confine che fa funzionare la crittografia a chiave pubblica. La pagina riporta la scomposizione e due conteggi, e nient'altro: non elenca i divisori stessi, non calcola un massimo comun divisore né un minimo comune multiplo su più numeri, e non semplifica radicali o frazioni. Un esponente di 1 non viene mai stampato, quindi un primo che compare una volta sola si mostra come un numero nudo, e il segno di moltiplicazione è un asterisco ovunque, il che significa che l'output è ASCII puro senza separatori di migliaia. Infine, la tabella di riferimento qui sotto mostra quattro numeri fissi invece di seguire il tuo ingresso.

Qual è la differenza fra i due conteggi di questa pagina?

Il primo conta i fattori primi tenendo le ripetizioni, il secondo conta i divisori. Per 12 le risposte sono 3 e 6, e sono giuste entrambe. Dodici è 2 × 2 × 3, quindi è fatto di tre pezzi primi; e 1, 2, 3, 4, 6 e 12 lo dividono tutti, quindi ha sei divisori. La confusione è naturale perché su ingressi piccoli i due numeri sono vicini. La ricetta del primo è sommare gli esponenti; la ricetta del secondo è sommare uno a ogni esponente e moltiplicare. Quella moltiplicazione è il motivo per cui il secondo conteggio scappa via molto più in fretta: ogni ripetizione in più di un primo moltiplica il numero di divisori mentre aggiunge solo uno al primo.

Esiste una sola scomposizione in fattori primi per ogni numero?

Sì, e questo è un teorema e non una convenzione. Ogni numero intero maggiore di 1 si può scrivere come prodotto di primi, e c'è esattamente un modo di farlo una volta ignorato l'ordine. Trecentosessanta è solo 2³ × 3² × 5; non è anche qualche altro prodotto di primi. Il risultato si chiama teorema fondamentale dell'aritmetica, e senza di esso stampare una scomposizione sarebbe una curiosità invece che una risposta. È anche il motivo per cui la pagina può stampare per primo il primo più piccolo ed essere sicura che quella sia la forma canonica: l'ordine è scelto per leggibilità, e fissarlo non fa perdere niente.

Che cosa fa la pagina con 1?

Stampa 1 come scomposizione, con zero fattori primi e un divisore. Uno non è né primo né composto: non ha una scomposizione in fattori primi nel senso usuale, ed è per questo che il teorema qui sopra si enuncia per i numeri maggiori di 1. Ma un pannello dei risultati vuoto si leggerebbe come un calcolo fallito, quindi la pagina stampa la cifra e riporta i due conteggi onestamente. Il numero di divisori di 1 è davvero 1, dato che l'unico numero positivo che divide 1 è 1 stesso, e il numero di fattori primi è davvero 0. Uno viene accettato invece che rifiutato perché l'intervallo di ingresso parte da 1, e rifiutare il fondo del proprio intervallo richiede più spiegazioni che rispondere.

Perché si ferma a un milione?

Perché il metodo è la divisione per tentativi, e il suo costo cresce con la radice quadrata del numero. Trovare i primi di un numero vicino a un milione significa provare divisori fino a mille, e è immediato. Trovare i primi di un numero di venti cifre significa provare fino a dieci miliardi, e non lo è. Quel divario non è un dettaglio realizzativo: è una proprietà reale del problema, ed è l'ipotesi su cui è costruita la crittografia a chiave pubblica, dove la difficoltà di fattorizzare numeri grandi è ciò che tiene privato un messaggio. Entro un milione ogni risposta torna immediatamente, e il tetto è dichiarato nell'ingresso invece che nascosto in un timeout.

Quando mi serve una scomposizione invece di un elenco di fattori?

Quando la domanda riguarda la struttura invece dell'appartenenza. Semplificare la radice quadrata di 72 richiede 72 = 2³ × 3², perché gli esponenti ti dicono quanto di ciascun primo può uscire da sotto il segno di radice, dando 6√2. Trovare un massimo comun divisore fra due numeri richiede entrambe le scomposizioni, dato che la risposta sono i primi in comune presi con l'esponente più piccolo. Controllare se un numero è un quadrato perfetto è uno sguardo agli esponenti: tutti pari significa sì. Elencare i divisori è una domanda diversa, e a seconda del numero può essere una risposta molto più lunga: 720.720 ne ha 240, che sono tanti da stampare e pochi da guardare. La pagina dei fattori di questo sito li elenca quando è quello che ti serve.

Perché non viene stampato nessun esponente quando un primo compare una volta sola?

Perché scrivere 5^1 per un singolo 5 è rumore. La convenzione in matematica è stampare un esponente solo quando è maggiore di uno, quindi 360 è 2^3 * 3^2 * 5 con l'ultimo termine nudo. Non si perde niente a toglierlo: l'assenza di esponente significa che l'esponente è uno, senza ambiguità, e una scomposizione fatta tutta di primi singoli — che è quello che ha un numero libero da quadrati — si legge come un prodotto semplice senza nessun accento circonflesso. La stessa convenzione è il motivo per cui 97, che è primo, si stampa come 97 e non come 97^1.

• Prime Factorization — writing a whole number as a product of primes, and the algorithms that find the primes — Wolfram MathWorld (United States)
• Fundamental Theorem of Arithmetic — the statement that every whole number above 1 has exactly one prime factorization, which is what makes printing it worth doing — Wolfram MathWorld (United States)
• Divisor Function — the count of positive divisors, the formula that builds it from the exponents, and how it behaves on powers of a single prime — Wolfram MathWorld (United States)
• Teoria dei numeri — lo studio delle proprietà dei numeri interi, fra cui la fattorizzazione unica e i divisori che questa pagina conta — Treccani, Istituto della Enciclopedia Italiana (Italia)