Calcolatore di fattorizzazione in numeri primi

Calcolatore di fattorizzazione in numeri primi - Scomponi i numeri

🔢 Scomponi qualsiasi numero nei suoi fattori primi. Visualizza i risultati come prodotto, con esponenti, albero dei fattori e processo di divisione passo dopo passo.

Cos’è la fattorizzazione in numeri primi?

La fattorizzazione in numeri primi (o fattorizzazione degli interi) è il processo di scomposizione di un numero composto in un prodotto di numeri primi. Ogni numero composto ha una fattorizzazione in primi unica.

Teorema fondamentale dell’aritmetica

Ogni intero maggiore di 1 può essere rappresentato in modo univoco come prodotto di numeri primi, a meno dell’ordine dei fattori. È uno dei teoremi più importanti della teoria dei numeri.

Formati di fattorizzazione

Forma di prodotto: 2 × 2 × 3 × 5

Forma esponenziale: 2² × 3 × 5

Forma indicizzata: 2² · 3¹ · 5¹

Esempi di fattorizzazione

Esempio 1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• Fattori primi: 2, 3

Esempio 2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• Fattori primi: 2, 3, 5

Esempio 3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• Fattori primi: 2, 5

Metodi di fattorizzazione

1. Divisione per tentativi:

• Dividi per i primi più piccoli (2, 3, 5, 7...)
• Continua finché il quoziente non è 1
• Semplice ma può essere lenta per numeri grandi

2. Albero dei fattori:

• Scomponi il numero in due fattori qualsiasi
• Continua finché tutti i fattori non sono primi
• Visivo e facile da capire

3. Divisione per primi:

• Dividi solo per numeri primi
• Più efficiente che provare tutti i numeri
• Algoritmo standard per i computer

Passo dopo passo: scomporre 60

60 ÷ 2 = 30   (2 è primo)
30 ÷ 2 = 15   (2 è primo)
15 ÷ 3 = 5    (3 è primo)
5 ÷ 5 = 1     (5 è primo)

Risultato: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

Trovare tutti i divisori

Una volta ottenuta la fattorizzazione, puoi trovare tutti i divisori:

Esempio: 60 = 2² × 3¹ × 5¹

• Per ogni primo, scegli un esponente da 0 al massimo
• 2⁰ o 2¹ o 2² → (1, 2, 4)
• 3⁰ o 3¹ → (1, 3)
• 5⁰ o 5¹ → (1, 5)
• Combina tutte le possibilità
• Divisori: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Formula per il numero di divisori

Se n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Numero di divisori = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

Esempio: 60 = 2² × 3¹ × 5¹

• Numero di divisori = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12 divisori

Formula per la somma dei divisori

Somma = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

Esempio: 60 = 2² × 3 × 5

• Somma = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

Applicazioni della fattorizzazione in primi

• Crittografia: la cifratura RSA dipende dalla difficoltà di fattorizzare grandi numeri
• MCD/mcm: trovare massimo comune divisore e minimo comune multiplo
• Semplificare frazioni: ridurre ai minimi termini
• Teoria dei numeri: studiare le proprietà degli interi
• Informatica: funzioni hash, algoritmi

Tipi speciali di numeri

Numeri perfetti:

• Uguali alla somma dei divisori propri
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

Numeri abbondanti:

• Somma dei divisori propri > numero
• 12: somma dei divisori = 1+2+3+4+6 = 16 > 12

Numeri difettivi:

• Somma dei divisori propri < numero
• 8: somma dei divisori = 1+2+4 = 7 < 8

Potenze di 2

I numeri che sono potenze di 2 hanno una fattorizzazione semplice:

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

Numeri altamente composti

Numeri con più divisori di qualsiasi intero positivo più piccolo:

• 1 (1 divisore)
• 2 (2 divisori)
• 4 (3 divisori)
• 6 (4 divisori)
• 12 (6 divisori)
• 24 (8 divisori)
• 36 (9 divisori)
• 60 (12 divisori)

Difficoltà della fattorizzazione

• Numeri piccoli: facili da fattorizzare a mano
• Primi grandi: molto difficili da fattorizzare
• Semiprimi: prodotto di due primi, base di RSA
• 200+ cifre: attualmente intrattabile con computer classici
• Computer quantistici: l’algoritmo di Shor può fattorizzare in modo efficiente

Fattorizzazioni comuni

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 Consiglio pro: Per controllare rapidamente la divisibilità per piccoli primi, ricorda: divisibile per 2 se l’ultima cifra è pari; per 3 se la somma delle cifre è divisibile per 3; per 5 se l’ultima cifra è 0 o 5; per 9 se la somma delle cifre è divisibile per 9; per 11 se la somma alternata delle cifre è divisibile per 11. Esempio: 4356, somma = 4+3+5+6 = 18 (divisibile per 9), quindi 4356 è divisibile per 9! Inizia con questi controlli prima di provare primi più grandi.