Divisores y Factorización

Divisores de un número

Un divisor de N es un número que divide a N sin dejar residuo. Ejemplo: los divisores de 12 son 12.

Encontrar todos los divisores: $O(\sqrt{n})$

vector<int> divisores(int n) {
    vector<int> divs;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i != n / i) {
                divs.push_back(n / i);
            }
        }
    }
    sort(divs.begin(), divs.end());
    return divs;
}

¿Por qué solo hasta $\sqrt{n}$? Los divisores vienen en parejas: si i divide a n, entonces n/i también. Solo necesitamos encontrar la mitad.

Ejemplo para n=36: encontramos (1,36), (2,18), (3,12), (4,9), (6,6).

Contar divisores

int contarDivisores(int n) {
    int cuenta = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cuenta++;
            if (i != n / i) cuenta++;
        }
    }
    return cuenta;
}

Factorización prima

Descomponer un número en sus factores primos. Ejemplo: $60 = 2^2 \times 3 \times 5$.

vector<pair<int,int>> factorizar(int n) {
    vector<pair<int,int>> factores;  // {primo, exponente}

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                n /= i;
                exp++;
            }
            factores.push_back({i, exp});
        }
    }
    if (n > 1) {
        factores.push_back({n, 1});  // El último factor primo
    }

    return factores;
}

Ejemplo

factorizar(360):

• $360 / 2 = 180, / 2 = 90, / 2 = 45$ → factor 3
• $45 / 3 = 15, / 3 = 5$ → factor 2
• $5 / 5 = 1$ → factor 1
• Resultado: $360 = 2^3 \times 3^2 \times 5$

Contar divisores usando factorización

Si $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$, entonces:

$\text{número de divisores} = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$

int contarDivisoresFact(int n) {
    int resultado = 1;
    for (auto [primo, exp] : factorizar(n)) {
        resultado *= (exp + 1);
    }
    return resultado;
}
// contarDivisoresFact(360) = (3+1)(2+1)(1+1) = 4×3×2 = 24

Suma de divisores

$\text{suma de divisores} = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1}$

long long sumaDivisores(int n) {
    long long resultado = 1;
    for (auto [p, a] : factorizar(n)) {
        long long suma = 0, potencia = 1;
        for (int i = 0; i <= a; i++) {
            suma += potencia;
            potencia *= p;
        }
        resultado *= suma;
    }
    return resultado;
}

Factorización rápida con criba SPF

Si necesitas factorizar muchos números, precalcula con la criba de menor factor primo:

const int MAXN = 1000005;
int spf[MAXN];

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

vector<pair<int,int>> factorizarRapido(int n) {
    vector<pair<int,int>> factores;
    while (n > 1) {
        int p = spf[n], e = 0;
        while (n % p == 0) { n /= p; e++; }
        factores.push_back({p, e});
    }
    return factores;
}

Ejercicio de práctica

Dado un número N, imprime su factorización prima y la cantidad total de divisores.

Entrada: 120 Salida:

2^3 * 3 * 5
Divisores: 16

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int,int>> factores;
    int temp = n;
    for (int i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            int e = 0;
            while (temp % i == 0) { temp /= i; e++; }
            factores.push_back({i, e});
        }
    }
    if (temp > 1) factores.push_back({temp, 1});

    // Imprimir factorización
    for (int i = 0; i < factores.size(); i++) {
        if (i > 0) cout << " * ";
        cout << factores[i].first;
        if (factores[i].second > 1) cout << "^" << factores[i].second;
    }
    cout << endl;

    // Contar divisores
    int divs = 1;
    for (auto [p, e] : factores) divs *= (e + 1);
    cout << "Divisores: " << divs << endl;

    return 0;
}