Descomposición en factores#11611

Descomposición en factores (Editorial)

Dado que es necesario factorizar muchos números que no superan $1 0^{7}$ 10^7, resulta conveniente realizar un precálculo. Mediante una versión modificada de la criba de Eratóstenes construimos un arreglo $s p f$ (smallest prime factor), donde

$s p f [i]$ contiene el menor divisor primo del número $i$

La factorización del número $n$ se realiza de la siguiente manera. Mientras $n > 1$ n > 1, tomamos $p = s p f [n]$ p = spf[n], el menor divisor primo del valor actual de $n$ , y dividimos $n$ entre $p$ mientras la división sea exacta, contando el exponente. Luego mostramos el factor $p$ elevado a la potencia correspondiente y pasamos al siguiente divisor primo. De este modo, los factores primos se obtienen en orden creciente, lo cual corresponde al formato de salida requerido.

La construcción de la criba requiere $O (n l o g l o g n)$ O(n~log~log~n) de tiempo. Cada división reduce $n$ al menos a la mitad, por lo que la factorización de un número se realiza en $O (l o g n)$ O(log~n). La complejidad temporal total para $q$ consultas es $O (n l o g l o g n + q l o g n)$ O(n~log~log~n + q~log~n).

Implementación del algoritmo

Declaremos un arreglo $s p f$ , en el que $s p f [i]$ contiene el menor divisor primo del número $i$ .

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

La función Sieve implementa la criba de Eratóstenes y llena el arreglo $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 función factorize descompone el número $n$ en factores primos, utilizando el arreglo $s p f$ .

void factorize(int n)
{

Extraemos los factores primos del número $n$ mientras este sea mayor que $1$ .

  while (n > 1)
  {

El menor divisor primo del número $n$ es igual a $p$ .

    int p = spf[n];

Encontramos la potencia máxima $p o w er$ para la cual $p^{p o w er}$ p^{power} divide al número $n$ .

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

Mostramos el factor $p^{p o w er}$ p^{power}.

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

Entre los factores se debe mostrar el signo ' $*$ '.

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

Parte principal del programa. Llenamos el arreglo $s p f$ utilizando la criba de Eratóstenes.

Sieve(MAX);

Para cada valor de entrada $n$ , mostramos su descomposición en factores primos.

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