The Lesson of Mathematics (Editoriale)

Il problema richiede di scomporre il numero $n$ in fattori primi, ossia di rappresentarlo nella forma n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}, dove p_1 < p_2 < ... < p_k — sono numeri primi. Ogni divisore primo p_i viene stampato insieme al suo esponente a_i, se a_i > 1.

Scorreremo i possibili divisori $i$ in ordine crescente, a partire da $2$. Se $i$ divide $n$, dividiamo $n$ per $i$ finché la divisione risulta esatta, contando il numero di divisioni $c$. Il valore $c$ ottenuto è proprio l'esponente con cui $i$ compare nella scomposizione. Successivamente stampiamo $i$, se c = 1, oppure i^c, se c > 1.

La ricerca dei divisori va effettuata fino a \sqrt{n}. Se il numero non ha divisori nell'intervallo da $2$ a \sqrt{n}, allora è primo. Pertanto, al termine del ciclo, il valore corrente di $n$ è uguale a $1$ oppure è un numero primo — l'ultimo fattore della scomposizione, che va anch'esso stampato. Un tale fattore "grande" può essere soltanto uno: il prodotto di due fattori maggiori di \sqrt{n} supererebbe $n$.

Esempio. Consideriamo n = 3240.

• i = 2: 3240 \to 1620 \to 810 \to 405, c = 3. Stampiamo 2^3*, poiché n = 405 > 1.

• i = 3: 405 \to 135 \to 45 \to 15 \to 5, c = 4. Stampiamo 3^4*, poiché n = 5 > 1.

• i = 4: 4 \cdot 4 > 5, il ciclo termina.

Il resto n = 5 > 1 è un fattore primo, stampiamo $5$.

Risposta: 2^3*3^4*5.

Implementazione dell'algoritmo

La funzione factor esegue la scomposizione del numero $n$ in fattori primi.

void factor(int n)
{
  for (int i = 2; i <= sqrt(n); i++)
  {
    if (n % i) continue;

Il numero $i$ è un divisore di $n$. Nella variabile $c$ contiamo l'esponente con cui compare nella scomposizione di $n$.

    int c = 0;
    while (n % i == 0) n /= i, c++;

Stampiamo il fattore i^c. Se l'esponente del fattore è c = 1, stampiamo solo $i$. Altrimenti, stampiamo il fattore $i$ con il suo esponente.

    if (c > 1) printf("%d^%d",i,c); else printf("%d",i);

Se il numero $n$ non è ancora completamente scomposto (n > 1), stampiamo il segno di moltiplicazione.

    if (n > 1) printf("*");
  }

Se, al termine del ciclo, il valore di $n$ è maggiore di $1$, allora è primo.

  if (n > 1) printf("%d",n);
  printf("\n");
}

Parte principale del programma. Leggiamo il numero in ingresso $n$ e avviamo la sua fattorizzazione.

scanf("%d",&n);
factor(n);

Implementazione in Python

import math

La funzione factor esegue la scomposizione del numero $n$ in fattori primi.

def factor(n):
  for i in range(2, math.isqrt(n) + 1):
    if n % i: continue

Il numero $i$ è un divisore di $n$. Nella variabile $c$ contiamo l'esponente con cui compare nella scomposizione di $n$.

    c = 0
    while n % i == 0:
      n //= i
      c += 1

Stampiamo il fattore i^c. Se l'esponente del fattore è c = 1, stampiamo solo $i$. Altrimenti, stampiamo il fattore $i$ con il suo esponente.

    if c > 1: print(i,"^",c, sep = "", end="")
    else: print(i, end="")

Se il numero $n$ non è ancora completamente scomposto (n > 1), stampiamo il segno di moltiplicazione.

    if n > 1: print("*", end="")

Se, al termine del ciclo, il valore di $n$ è maggiore di $1$, allora è primo.

  if n > 1: print(n)
  else: print()

Parte principale del programma. Leggiamo il numero in ingresso $n$ e avviamo la sua fattorizzazione.

n = int(input())
factor(n)