Factorización

Tema: Matemática y Combinatoria · temarios: Syllabus OCI · Syllabus IOI

📍 Ampliación: parte de divisibilidad y MCD del módulo 10. Esta técnica se desarrolla en la ficha, no en esa clase.

Qué problema resuelve

Factorizar un entero positivo es escribirlo como producto de primos. Por ejemplo, 360 = 2³ · 3² · 5. La función devuelve pares {primo, exponente}: para 360, {{2,3},{3,2},{5,1}}. El 1 produce una lista vacía; 0 y los números negativos quedan fuera del contrato.

La descomposición sirve para estudiar divisibilidad, cantidad de divisores y propiedades de productos sin construir necesariamente esos productos. Antes de usarla, estima el costo según el valor del número, no solo según cuántos números recibes.

Dividir y achicar el problema

Probamos divisores p desde 2. Cuando uno divide el valor restante, lo extraemos todas las veces que sea posible y contamos su exponente.

Divisor probadoRestante antesDivisionesRestante después
2360360 → 180 → 90 → 4545
34545 → 15 → 55

Ahora el siguiente candidato sería 4, pero 4² > 5, así que detenemos el bucle. El 5 restante se agrega como factor primo con exponente 1.

Aunque recorremos también candidatos compuestos, ninguno puede dividir el restante: sus factores primos menores ya se extrajeron completamente. Por eso todo divisor que realmente encontramos es primo.

Por qué podemos detenernos en la raíz

Si un entero es compuesto, se puede escribir x = a*b con 1 < a <= b, y entonces a <= √x. Si ya no queda divisor hasta la raíz del valor restante, ese restante solo puede ser 1 o primo.

La raíz se aplica al valor que va quedando, no necesariamente al número original. Extraer factores puede terminar el trabajo antes. La condición p <= n/p expresa p*p <= n para enteros positivos sin arriesgar desbordamiento en el producto.

Implementación recomendada (C++)

// Factores primos de n con sus exponentes: {primo, exponente}.
vector<pair<long long,int>> factorize(long long n) {
    vector<pair<long long,int>> f;
    for (long long p = 2; p <= n / p; p++)
        if (n % p == 0) { int e = 0; while (n % p == 0) { n /= p; e++; } f.push_back({p, e}); }
    if (n > 1) f.push_back({n, 1});
    return f;
}

Costo: O(√n) tiempo en el peor caso, por ejemplo cuando el número original es primo. La lista de factores usa O(log n) espacio como cota superior. El valor de n se recibe por copia: dividirlo dentro de la función no modifica la variable con la que la llamaste.

Un número cercano a 10^12 puede exigir cerca de un millón de intentos; cien mil números así cambian completamente el costo total. Cerca de 10^18, la raíz es mil millones: esta implementación no es una solución rápida general para ese rango. Evitar overflow no elimina ese costo.

Para muchos valores dentro de un límite moderado, consulta Criba de Eratóstenes y considera precalcular primos o el menor factor primo. No reserves una tabla hasta un valor enorme solo porque haya pocas consultas.

Para comprobarlo

Factoriza 84, 49, 97 y 1. Debes obtener 2²·3·7, 7², 97 y ningún factor, respectivamente. El caso 97 permite comprobar el último if (n > 1); el 49 comprueba que no debes cambiar <= por < en la condición del bucle.