Calcolare i Divisori di un Numero Intero: Guida Completa e Dettagliata

La determinazione del numero di divisori di un numero intero è un concetto fondamentale in teoria dei numeri e trova applicazione in vari ambiti, dalla crittografia all’ottimizzazione algoritmica. Comprendere come calcolare questo valore non solo rafforza le tue basi matematiche, ma ti fornisce anche uno strumento utile per risolvere problemi complessi. In questo articolo, esploreremo in dettaglio i metodi per trovare i divisori di un numero intero, con esempi pratici e spiegazioni chiare, partendo dai concetti di base fino ad arrivare a tecniche più avanzate.

Cos’è un Divisore?

Prima di addentrarci nei metodi di calcolo, è essenziale definire cosa si intende per divisore. Un divisore (o fattore) di un numero intero ‘n’ è un altro numero intero ‘d’ che divide ‘n’ senza lasciare resto. In altre parole, se ‘n’ diviso per ‘d’ restituisce un numero intero, allora ‘d’ è un divisore di ‘n’. Ad esempio, i divisori di 12 sono 1, 2, 3, 4, 6 e 12, perché ciascuno di questi numeri divide 12 esattamente senza lasciare resto. I divisori vengono anche detti fattori e nella scomposizione di un numero nei suoi fattori primi sono fondamentali.

Metodi per Determinare i Divisori

Esistono diversi approcci per determinare i divisori di un numero intero. Analizziamo i principali:

1. Metodo della Divisione per Tentativi

Questo è il metodo più intuitivo e diretto, particolarmente utile per numeri piccoli. L’idea è semplice: si controlla se ogni numero intero da 1 fino al numero stesso è un divisore. Se la divisione non ha resto, allora abbiamo trovato un divisore. Vediamo i passaggi:

1. Inizializzazione: Inizia con un numero ‘n’ del quale vuoi trovare i divisori.
2. Iterazione: Crea un ciclo che scorra tutti i numeri interi ‘i’ da 1 fino a ‘n’.
3. Verifica: Per ogni numero ‘i’, calcola ‘n’ modulo ‘i’ (il resto della divisione di ‘n’ per ‘i’).
4. Aggiungi divisore: Se il resto è zero, allora ‘i’ è un divisore di ‘n’, quindi aggiungilo alla lista dei divisori.
5. Fine: Quando il ciclo termina, avrai raccolto tutti i divisori di ‘n’.

Esempio: Troviamo i divisori di 20 usando questo metodo.

• n = 20
• i = 1: 20 % 1 = 0. 1 è un divisore.
• i = 2: 20 % 2 = 0. 2 è un divisore.
• i = 3: 20 % 3 = 2. 3 non è un divisore.
• i = 4: 20 % 4 = 0. 4 è un divisore.
• i = 5: 20 % 5 = 0. 5 è un divisore.
• i = 6: 20 % 6 = 2. 6 non è un divisore.
• i = 7: 20 % 7 = 6. 7 non è un divisore.
• i = 8: 20 % 8 = 4. 8 non è un divisore.
• i = 9: 20 % 9 = 2. 9 non è un divisore.
• i = 10: 20 % 10 = 0. 10 è un divisore.
• i = 11-19: Nessuno di questi è un divisore.
• i = 20: 20 % 20 = 0. 20 è un divisore.

I divisori di 20 sono quindi: 1, 2, 4, 5, 10, 20.

Ottimizzazione: Una piccola ottimizzazione consiste nell’iterare solo fino alla radice quadrata di ‘n’. Questo perché i divisori di un numero si presentano in coppie. Ad esempio, se ‘d’ è un divisore di ‘n’, allora anche ‘n/d’ è un divisore. Quindi, se troviamo ‘d’ <= √n, troviamo automaticamente anche il divisore ‘n/d’. Ad esempio, nel caso di 20, dobbiamo cercare solo fino a √20 ≈ 4.47. In questo modo, i divisori trovati saranno 1, 2 e 4. Da questi, possiamo ricavare 20/1 = 20, 20/2 = 10 e 20/4 = 5. In questo caso, dobbiamo fare una attenzione in più, perché la radice quadrata può essere un numero intero (esempio: 16, la cui radice è 4) e quindi il numero deve essere aggiunto una sola volta.

def trova_divisori_tentativi(n):
    divisori = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisori.append(i)
            if i != n // i:
                divisori.append(n // i)
    divisori.sort()
    return divisori

print(trova_divisori_tentativi(20))
# Output: [1, 2, 4, 5, 10, 20]

print(trova_divisori_tentativi(16))
# Output: [1, 2, 4, 8, 16]

2. Metodo della Scomposizione in Fattori Primi

Questo metodo è più elegante e potente, soprattutto quando si ha a che fare con numeri grandi. Si basa sul teorema fondamentale dell’aritmetica, il quale afferma che ogni numero intero maggiore di 1 può essere espresso in modo unico come prodotto di potenze di numeri primi. Una volta ottenuta la scomposizione, possiamo facilmente calcolare il numero totale di divisori.

Passaggi:

1. Scomposizione: Trova la scomposizione in fattori primi del numero ‘n’. Ad esempio, 36 = 2² * 3².
2. Esponenti: Prendi gli esponenti di ciascun fattore primo e aggiungi 1 a ciascuno di essi. Ad esempio, per 36, gli esponenti sono 2 e 2, quindi aggiungiamo 1, ottenendo 3 e 3.
3. Moltiplicazione: Moltiplica tutti i risultati ottenuti al passo precedente. Nel caso di 36, 3 * 3 = 9. Il numero totale di divisori di 36 è 9.

Esempio: Calcoliamo i divisori di 120 utilizzando questo metodo.

• Scomposizione di 120: 120 = 2³ * 3¹ * 5¹
• Esponenti + 1: Gli esponenti sono 3, 1 e 1. Aggiungiamo 1 ottenendo 4, 2 e 2.
• Moltiplicazione: 4 * 2 * 2 = 16. Ci sono 16 divisori di 120.

Esempio: Calcoliamo i divisori di 100 usando la scomposizione in fattori primi

• Scomposizione di 100: 100 = 2² * 5²
• Esponenti + 1: Gli esponenti sono 2 e 2. Aggiungiamo 1 ottenendo 3 e 3
• Moltiplicazione: 3*3 = 9. Ci sono 9 divisori di 100.

Per trovare i divisori, li possiamo ricavare dalle combinazioni dei fattori primi. Ad esempio, nel caso di 120, possiamo considerare 2⁰, 2¹, 2², 2³ , 3⁰, 3¹, 5⁰, 5¹. Tutti i divisori saranno tutte le possibili combinazioni tra questi fattori primi. Nello specifico i divisori di 120 sono:
1 (2⁰ * 3⁰ * 5⁰), 2 (2¹ * 3⁰ * 5⁰), 3 (2⁰ * 3¹ * 5⁰), 4 (2² * 3⁰ * 5⁰), 5 (2⁰ * 3⁰ * 5¹), 6 (2¹ * 3¹ * 5⁰), 8 (2³ * 3⁰ * 5⁰), 10 (2¹ * 3⁰ * 5¹), 12 (2² * 3¹ * 5⁰), 15 (2⁰ * 3¹ * 5¹), 20 (2² * 3⁰ * 5¹), 24 (2³ * 3¹ * 5⁰), 30 (2¹ * 3¹ * 5¹), 40 (2³ * 3⁰ * 5¹), 60 (2² * 3¹ * 5¹), 120 (2³ * 3¹ * 5¹).

La scomposizione in fattori primi può essere ottenuta attraverso un semplice algoritmo.

def scomposizione_fattori_primi(n):
  fattori = []
  d = 2
  while d * d <= n:
    while n % d == 0:
      fattori.append(d)
      n //= d
    d += 1
  if n > 1:
    fattori.append(n)
  return fattori

def calcola_numero_divisori(n):
  fattori_primi = scomposizione_fattori_primi(n)
  esponenti = {}
  for fattore in fattori_primi:
    esponenti[fattore] = esponenti.get(fattore, 0) + 1
  numero_divisori = 1
  for esponente in esponenti.values():
    numero_divisori *= (esponente + 1)
  return numero_divisori


print(calcola_numero_divisori(120))
# Output: 16

print(calcola_numero_divisori(36))
# Output: 9

print(calcola_numero_divisori(100))
# Output: 9

3. Metodo Ricorsivo

Sebbene meno efficiente dal punto di vista pratico per numeri grandi, un approccio ricorsivo può essere utile per comprendere meglio la struttura del problema. La ricorsione consiste nel suddividere un problema in sottoproblemi più piccoli della stessa natura fino a raggiungere una condizione base di semplice risoluzione. Nel nostro caso, possiamo definire una funzione ricorsiva che calcola i divisori di un numero ‘n’ controllando i divisori a partire da 1 e fino alla radice quadrata di n. In questa implementazione, se un numero è un divisore, la funzione ricorsivamente cerca i divisori del numero n/d, aggiungendoli alla lista dei divisori. Questo metodo è più didattico che efficiente, in quanto ricorsivamente si controllano gli stessi divisori più volte.

def trova_divisori_ricorsivo(n, d=1, divisori=None):
    if divisori is None:
        divisori = []
    if d * d > n:
        divisori.sort()
        return divisori
    if n % d == 0:
        divisori.append(d)
        if d != n // d:
            divisori.append(n//d)

    return trova_divisori_ricorsivo(n, d + 1, divisori)

print(trova_divisori_ricorsivo(20))
# Output: [1, 2, 4, 5, 10, 20]

print(trova_divisori_ricorsivo(16))
# Output: [1, 2, 4, 8, 16]

Implementazione in Python

Di seguito, forniamo un codice completo in Python per calcolare i divisori di un numero intero utilizzando i metodi descritti:

import math

def trova_divisori_tentativi(n):
    divisori = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisori.append(i)
            if i != n // i:
                divisori.append(n // i)
    divisori.sort()
    return divisori

def scomposizione_fattori_primi(n):
  fattori = []
  d = 2
  while d * d <= n:
    while n % d == 0:
      fattori.append(d)
      n //= d
    d += 1
  if n > 1:
    fattori.append(n)
  return fattori

def calcola_numero_divisori(n):
  fattori_primi = scomposizione_fattori_primi(n)
  esponenti = {}
  for fattore in fattori_primi:
    esponenti[fattore] = esponenti.get(fattore, 0) + 1
  numero_divisori = 1
  for esponente in esponenti.values():
    numero_divisori *= (esponente + 1)
  return numero_divisori

def trova_divisori_ricorsivo(n, d=1, divisori=None):
    if divisori is None:
        divisori = []
    if d * d > n:
        divisori.sort()
        return divisori
    if n % d == 0:
        divisori.append(d)
        if d != n // d:
            divisori.append(n//d)

    return trova_divisori_ricorsivo(n, d + 1, divisori)


# Esempi di utilizzo

n = 20
print(f"I divisori di {n} (metodo dei tentativi) sono: {trova_divisori_tentativi(n)}")
print(f"I divisori di {n} (metodo ricorsivo) sono: {trova_divisori_ricorsivo(n)}")
print(f"Il numero di divisori di {n} (scomposizione in fattori primi) è: {calcola_numero_divisori(n)}")

n = 36
print(f"I divisori di {n} (metodo dei tentativi) sono: {trova_divisori_tentativi(n)}")
print(f"I divisori di {n} (metodo ricorsivo) sono: {trova_divisori_ricorsivo(n)}")
print(f"Il numero di divisori di {n} (scomposizione in fattori primi) è: {calcola_numero_divisori(n)}")

n = 120
print(f"I divisori di {n} (metodo dei tentativi) sono: {trova_divisori_tentativi(n)}")
print(f"I divisori di {n} (metodo ricorsivo) sono: {trova_divisori_ricorsivo(n)}")
print(f"Il numero di divisori di {n} (scomposizione in fattori primi) è: {calcola_numero_divisori(n)}")

n = 100
print(f"I divisori di {n} (metodo dei tentativi) sono: {trova_divisori_tentativi(n)}")
print(f"I divisori di {n} (metodo ricorsivo) sono: {trova_divisori_ricorsivo(n)}")
print(f"Il numero di divisori di {n} (scomposizione in fattori primi) è: {calcola_numero_divisori(n)}")


# Output:
# I divisori di 20 (metodo dei tentativi) sono: [1, 2, 4, 5, 10, 20]
# I divisori di 20 (metodo ricorsivo) sono: [1, 2, 4, 5, 10, 20]
# Il numero di divisori di 20 (scomposizione in fattori primi) è: 6
# I divisori di 36 (metodo dei tentativi) sono: [1, 2, 3, 4, 6, 9, 12, 18, 36]
# I divisori di 36 (metodo ricorsivo) sono: [1, 2, 3, 4, 6, 9, 12, 18, 36]
# Il numero di divisori di 36 (scomposizione in fattori primi) è: 9
# I divisori di 120 (metodo dei tentativi) sono: [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
# I divisori di 120 (metodo ricorsivo) sono: [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
# Il numero di divisori di 120 (scomposizione in fattori primi) è: 16
# I divisori di 100 (metodo dei tentativi) sono: [1, 2, 4, 5, 10, 20, 25, 50, 100]
# I divisori di 100 (metodo ricorsivo) sono: [1, 2, 4, 5, 10, 20, 25, 50, 100]
# Il numero di divisori di 100 (scomposizione in fattori primi) è: 9

Conclusione

La capacità di determinare il numero di divisori di un numero intero è un’abilità fondamentale in matematica e informatica. In questo articolo, abbiamo esaminato diversi approcci, dal metodo della divisione per tentativi, passando per la scomposizione in fattori primi, fino all’approccio ricorsivo. La scelta del metodo più appropriato dipende dal contesto e dalla dimensione del numero. La scomposizione in fattori primi si dimostra particolarmente efficiente per calcolare il numero dei divisori di numeri grandi, mentre la divisione per tentativi è più semplice da comprendere e applicare per numeri più piccoli. Con l’implementazione fornita in Python, avrai a disposizione strumenti pratici per esplorare ulteriormente questo concetto affascinante.

Speriamo che questa guida ti sia stata utile e che ti abbia fornito le conoscenze necessarie per affrontare questo tipo di problema con sicurezza. Se hai altre domande o argomenti che vorresti approfondire, non esitare a chiedere!