Scomposizione in fattori#11611

Scomposizione in fattori (Editoriale)

Poiché è richiesto fattorizzare molti numeri non superiori a $1 0^{7}$ 10^7, conviene eseguire un precalcolo. Utilizzando una versione modificata del crivello di Eratostene, costruiamo l'array $s p f$ (smallest prime factor), dove

$s p f [i]$ contiene il più piccolo divisore primo del numero $i$

La fattorizzazione del numero $n$ viene eseguita nel modo seguente. Finché $n > 1$ n > 1, prendiamo $p = s p f [n]$ p = spf[n], il più piccolo divisore primo del valore corrente di $n$ , e dividiamo $n$ per $p$ finché la divisione risulta esatta, contando l'esponente. Successivamente stampiamo il fattore $p$ elevato alla potenza corrispondente e passiamo al divisore primo successivo. I fattori primi vengono così ottenuti in ordine crescente, il che corrisponde al formato di output richiesto.

La costruzione del crivello richiede un tempo $O (n l o g l o g n)$ O(n~log~log~n). Ogni divisione riduce $n$ di almeno la metà, quindi la fattorizzazione di un singolo numero viene eseguita in $O (l o g n)$ O(log~n). La complessità temporale totale per $q$ richieste è pari a $O (n l o g l o g n + q l o g n)$ O(n~log~log~n + q~log~n).

Implementazione dell'algoritmo

Dichiariamo l'array $s p f$ , in cui $s p f [i]$ contiene il più piccolo divisore primo del numero $i$ .

#define MAX 10000001
int spf[MAX + 1];

La funzione Sieve implementa il crivello di Eratostene e riempie l'array $s p f$ .

void Sieve(int n)
{
  for (int i = 0; i < n; i++)
    spf[i] = i;
  for (int i = 2; i <= sqrt(n); i++)
    if (spf[i] == i)
      for (int j = i * i; j < n; j += i)
        if (spf[j] == j) spf[j] = i;
}

C++

La funzione factorize scompone il numero $n$ nei suoi fattori primi, utilizzando l'array $s p f$ .

void factorize(int n)
{

Estraiamo i fattori primi dal numero $n$ finché esso è maggiore di $1$ .

  while (n > 1)
  {

Il più piccolo divisore primo del numero $n$ è uguale a $p$ .

    int p = spf[n];

Troviamo la potenza massima $p o w er$ per cui $p^{p o w er}$ p^{power} divide il numero $n$ .

    int power = 0;
    while (n % p == 0)
    {
      n /= p;
      power++;
    }

Stampiamo il fattore $p^{p o w er}$ p^{power}.

    if (power > 1) printf("%d^%d", p, power); else printf("%d", p);

Tra i fattori va stampato il simbolo ' $*$ '.

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

Parte principale del programma. Riempiamo l'array $s p f$ utilizzando il crivello di Eratostene.

Sieve(MAX);

Per ogni valore di input $n$ stampiamo la sua scomposizione in fattori primi.

while (scanf("%d", &n) == 1)
  factorize(n);