Contando Divisores: De lo Básico a lo Optimizado en C++

En el fascinante mundo de la aritmética y la programación, una de las operaciones fundamentales es la de determinar cuántos divisores tiene un número entero dado. Los divisores son aquellos números que dividen a otro de forma exacta, sin dejar residuo. Contar divisores es una habilidad esencial no solo para resolver problemas matemáticos, sino también en campos como la criptografía, la teoría de números y la optimización de algoritmos. En este artículo, exploraremos diferentes enfoques para abordar este problema en C++, desde una solución simple pero menos eficiente hasta un método avanzado que optimiza drásticamente el tiempo de ejecución.

Comprender los divisores de un número es el primer paso. Por ejemplo, para el número 18, sus divisores son 1, 2, 3, 6, 9 y 18. Para el número 100, sus divisores son 1, 2, 4, 5, 10, 20, 25, 50 y 100. Contar estos elementos de manera sistemática y eficiente es nuestro objetivo principal.

Enfoque 1: El Método Ingénuo (Complejidad O(sqrt(n)))

La forma más directa y sencilla de contar los divisores de un número n es iterar desde 1 hasta la raíz cuadrada de n. Por cada número i en este rango, verificamos si i divide a n. Si lo hace, entonces i es un divisor. Además, n/i también será un divisor. Es importante manejar un caso especial: si i * i es igual a n (es decir, n es un cuadrado perfecto y i es su raíz cuadrada), entonces i y n/i son el mismo número, y solo debemos contarlo una vez para evitar duplicados. De lo contrario, contamos tanto a i como a n/i.

Explicación del Algoritmo Ingénuo

Este método se basa en la propiedad de que los divisores siempre vienen en pares. Si i es un divisor de n, entonces n/i también lo es. Si i < sqrt(n), entonces n/i > sqrt(n). Si i > sqrt(n), entonces n/i < sqrt(n). Esto significa que al iterar solo hasta sqrt(n), cubrimos todos los pares de divisores. El caso especial ocurre cuando i = sqrt(n), lo que significa que i = n/i, y por lo tanto, ese divisor se cuenta solo una vez.

Implementación en C++ del Método Ingénuo

A continuación, se presenta el código C++ que implementa esta lógica. Es un enfoque claro y fácil de entender, ideal para números pequeños o cuando la simplicidad es prioritaria sobre la eficiencia extrema.

#include <bits/stdc++.h> using namespace std; // función para contar los divisores int countDivisors(int n) { int cnt = 0; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // Si los divisores son iguales, // cuenta solo uno if (n / i == i) cnt++; else // De lo contrario, cuenta ambos cnt = cnt + 2; } } return cnt; } /* Programa principal para probar la función */ int main() { cout << "Total de divisores distintos de 100 son " << countDivisors(100) << endl; return 0; }

Análisis de Complejidad

• Complejidad Temporal: O(sqrt(n)). Esto se debe a que el bucle principal se ejecuta aproximadamente sqrt(n) veces. La operación % (módulo) y / (división) son operaciones de tiempo constante.
• Complejidad Espacial: O(1). No se utiliza espacio adicional que dependa del tamaño de n más allá de unas pocas variables.

Aunque este método es simple, su eficiencia disminuye considerablemente a medida que n se vuelve muy grande. Para números extremadamente grandes, necesitamos una estrategia más inteligente.

Enfoque 2: Solución Optimizada (Complejidad O(n^1/3))

Para números grandes, el método ingenuo puede ser demasiado lento. Una solución más optimizada se basa en el teorema fundamental de la aritmética, que establece que todo número entero mayor que 1 puede ser representado de forma única como un producto de factores primos. Si n = p1^e1 * p2^e2 * p3^e3 * ... * pk^ek, donde p1, p2, ..., pk son factores primos distintos y e1, e2, ..., ek son sus respectivos exponentes, entonces el número total de divisores de n es (e1+1) * (e2+1) * (e3+1) * ... * (ek+1).

El enfoque optimizado utiliza esta propiedad junto con una técnica para encontrar los factores primos de manera eficiente hasta la raíz cúbica de n. La idea es encontrar los factores primos pequeños (aquellos menores o iguales a n^(1/3)) y sus exponentes. Lo que queda del número después de dividirlo por estos factores pequeños tendrá una estructura particular que nos permite determinar sus divisores restantes de forma rápida.

La Criba de Eratóstenes como Preprocesamiento

Para encontrar los factores primos pequeños de manera eficiente, podemos usar la Criba de Eratóstenes. Esta es una forma efectiva de encontrar todos los números primos hasta un límite dado. En este algoritmo, la criba se utiliza para precalcular los números primos hasta n y también para identificar los cuadrados de los números primos.

void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]) { // Inicializa todos los números como primos true for (int i = 2; i <= n; i++) prime[i] = true; // Inicializa todos los cuadrados de primos como false for (int i = 0; i <= (n * n + 1); i++) primesquare[i] = false; // 1 no es un número primo prime[1] = false; // Implementación de la Criba de Eratóstenes for (int p = 2; p * p <= n; p++) { // Si prime[p] no ha cambiado, entonces es un primo if (prime[p] == true) { // Actualiza todos los múltiplos de p a partir de p*p for (int i = p * p; i <= n; i += p) prime[i] = false; } } int j = 0; // Almacena los primos en el array 'a' for (int p = 2; p <= n; p++) { if (prime[p]) { a[j] = p; // Marca los cuadrados de los primos primesquare[p * p] = true; j++; } } }

Lógica Principal del Conteo de Divisores (O(n^1/3))

Después de precalcular los primos, el algoritmo principal itera a través de los números primos a[i] (obtenidos de la criba) y los utiliza para dividir n hasta que a[i]^3 sea mayor que el n restante. Esto asegura que solo estamos factorizando por primos menores o iguales a la raíz cúbica de n. Para cada primo a[i] que divide a n, contamos cuántas veces divide a n (es decir, su exponente cnt) y luego multiplicamos (cnt+1) al número total de divisores.

Lo más interesante de este enfoque es cómo maneja el número restante después de que todos los factores primos menores o iguales a n^(1/3) han sido extraídos. Llamemos a este número restante Y. La clave es que Y no puede tener más de dos factores primos distintos. Demostremos esto por contradicción:

• Supongamos que Y tiene tres factores primos distintos: p1, p2, p3.
• Por cómo el algoritmo funciona, todos estos factores primos deben ser mayores que n^(1/3) (porque todos los primos menores o iguales a n^(1/3) ya han sido extraídos).
• Entonces, p1 > n^(1/3), p2 > n^(1/3), y p3 > n^(1/3).
• Esto implicaría que p1 * p2 * p3 > n^(1/3) * n^(1/3) * n^(1/3) = n.
• Pero Y = p1 * p2 * p3 es un factor de n, lo que significa que Y <= n.
• Esto es una contradicción, lo que prueba que Y no puede tener más de dos factores primos distintos.

Basado en esta prueba, Y solo puede caer en una de tres categorías:

1. Y es un número primo: (ej. Y = p). Su exponente es 1, por lo que contribuye (1+1) = 2 a los divisores.
2. Y es el cuadrado de un número primo: (ej. Y = p^2). Su exponente es 2, por lo que contribuye (2+1) = 3 a los divisores.
3. Y es un número compuesto con dos factores primos distintos: (ej. Y = p1 * p2, donde p1 != p2). Cada uno tiene un exponente de 1, por lo que contribuye (1+1)*(1+1) = 2*2 = 4 a los divisores.

El algoritmo verifica cuál de estos casos aplica a Y y multiplica el factor correspondiente al total de divisores acumulados.

Implementación en C++ del Método Optimizado

El siguiente código C++ demuestra esta compleja pero eficiente estrategia:

#include <bits/stdc++.h> using namespace std; // Se incluye la función SieveOfEratosthenes aquí (tal como se mostró arriba) // ... // Función para contar divisores int countDivisors(int n) { // Si el número es 1, solo tiene 1 divisor if (n == 1) return 1; // Arrays para la criba y almacenamiento de primos bool prime[n + 1], primesquare[n * n + 1]; int a[n]; // para almacenar primos hasta n // Llama a la Criba de Eratóstenes SieveOfEratosthenes(n, prime, primesquare, a); // ans contendrá el número total de divisores distintos int ans = 1; // Bucle para contar factores de n for (int i = 0; ; i++) { // a[i] no es menor que la raíz cúbica de n if (a[i] * a[i] * a[i] > n) break; // Calcula la potencia de a[i] en n. int cnt = 1; // cnt es la potencia del primo a[i] en n. while (n % a[i] == 0) // si a[i] es un factor de n { n = n / a[i]; cnt = cnt + 1; // incrementa la potencia } // Calcula el número de divisores ans = ans * cnt; } // Si a[i] es mayor que la raíz cúbica de n // Primer caso: El número restante es primo if (prime[n]) ans = ans * 2; // Segundo caso: El número restante es el cuadrado de un primo else if (primesquare[n]) ans = ans * 3; // Tercer caso: El número restante es compuesto con dos factores primos distintos else if (n != 1) ans = ans * 4; return ans; // Total de divisores } // Programa principal int main() { cout << "Total de divisores distintos de 100 son: " << countDivisors(100) << endl; return 0; }

Análisis de Complejidad

• Complejidad Temporal: O(N log log N + n^(1/3)). La parte de la criba es O(N log log N) donde N es el valor máximo de n que la criba puede manejar. La parte de factorización en el bucle principal es O(n^(1/3)) porque solo se itera hasta la raíz cúbica de n. Para un único llamado a countDivisors(n) donde la criba se ejecuta hasta n, la complejidad efectiva es dominada por la criba. Sin embargo, si la criba es una precomputación global y la función se llama muchas veces, la parte de n^(1/3) es la relevante por llamada. El enunciado proporcionado indica O(n^1/3), lo que asume una criba precalculada o que el costo dominante es la parte de factorización para números grandes después de la criba.
• Complejidad Espacial: O(n). Esto se debe al uso de los arrays prime, primesquare y a en la Criba de Eratóstenes, que crecen linealmente con n.

Este método es significativamente más rápido para números grandes, a costa de una mayor complejidad en la implementación y un mayor uso de memoria para la criba.

Comparación de Enfoques

Fórmula Matemática para Contar Divisores

Más allá de los algoritmos de programación, existe una elegante fórmula matemática para calcular el número de divisores de un número n. Esta fórmula se deriva directamente de la descomposición en factores primos de n.

Si un número natural n se puede expresar como un producto de sus factores primos elevados a sus respectivas potencias:

n = p1^e1 * p2^e2 * p3^e3 * ... * pk^ek

Donde p1, p2, ..., pk son números primos distintos, y e1, e2, ..., ek son sus exponentes (números enteros positivos).

Entonces, el número total de divisores de n, denotado como d(n) o tau(n), se calcula como el producto de cada exponente incrementado en uno:

d(n) = (e1 + 1) * (e2 + 1) * (e3 + 1) * ... * (ek + 1)

Ejemplo: Calculemos los divisores de 48 usando esta fórmula.

1. Primero, descomponemos 48 en sus factores primos:48 = 2 * 24 = 2 * 2 * 12 = 2 * 2 * 2 * 6 = 2 * 2 * 2 * 2 * 3 = 2^4 * 3^1
2. Aquí, los factores primos son p1 = 2 con exponente e1 = 4, y p2 = 3 con exponente e2 = 1.
3. Aplicamos la fórmula:d(48) = (e1 + 1) * (e2 + 1) = (4 + 1) * (1 + 1) = 5 * 2 = 10

Así, 48 tiene 10 divisores, que son: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Esta fórmula es la base matemática sobre la que se construye el algoritmo optimizado, ya que ambos se basan en la obtención de los exponentes de los factores primos.

¿Cómo Hallar la Cantidad de Divisores Compuestos de un Número?

Además de contar el total de divisores, a menudo surge la pregunta de cuántos de esos divisores son compuestos. Un divisor es compuesto si tiene más de dos divisores (es decir, no es primo y no es 1).

Para hallar la cantidad de divisores compuestos de un número n, podemos seguir estos pasos:

1. Calcular el número total de divisores: Usa cualquiera de los métodos anteriores (ingénuo, optimizado, o la fórmula matemática d(n) = (e1+1)...) para encontrar d(n).
2. Calcular el número de divisores primos: Identifica todos los números primos que son divisores de n. Por ejemplo, para 100, los divisores primos son 2 y 5. Para 18, son 2 y 3.
3. Restar los divisores no compuestos: Los divisores que no son compuestos son el número 1 y los números primos que dividen a n.

La fórmula general sería:

Número de Divisores Compuestos = (Total de Divisores) - (Número de Divisores Primos) - 1

El -1 es para excluir el número 1, ya que 1 no es ni primo ni compuesto.

Ejemplo: Para n = 100:

• Total de divisores d(100) = 9 (1, 2, 4, 5, 10, 20, 25, 50, 100).
• Divisores primos de 100: 2 y 5 (hay 2 divisores primos).
• Número de divisores compuestos = 9 - 2 - 1 = 6.

Los divisores compuestos de 100 son: 4, 10, 20, 25, 50, 100. Contamos 6, lo que coincide con nuestra fórmula.

Preguntas Frecuentes

¿Cuántos divisores tiene un número?

La cantidad de divisores que tiene un número entero se puede determinar de varias maneras. Para números pequeños, puedes listarlos manualmente y contarlos. Por ejemplo, para 48, podemos ver que 48 = 1×48 = 2×24 = 3×16 = 4×12 = 6×8. Al contar todos los números únicos en estos pares, obtenemos 10 divisores (1, 2, 3, 4, 6, 8, 12, 16, 24, 48). Para un método más sistemático y aplicable a números grandes, se utiliza la fórmula basada en la factorización prima del número. Si n = p1^e1 * p2^e2 * ... * pk^ek, entonces el número de divisores es (e1+1) * (e2+1) * ... * (ek+1).

¿Cuál es la diferencia entre un divisor primo y un divisor compuesto?

Un divisor primo es un número primo que divide a un número dado. Por ejemplo, para 12, los divisores son 1, 2, 3, 4, 6, 12. Los divisores primos son 2 y 3. Un divisor compuesto es un número compuesto que divide a un número dado. Para 12, los divisores compuestos son 4, 6 y 12. El número 1 no es ni primo ni compuesto, y siempre es un divisor de cualquier número entero.

¿Es el número 1 un divisor de todos los números?

Sí, el número 1 es un divisor de todo número entero. Cualquier número entero dividido por 1 resulta en el mismo número entero, sin residuo.

¿Qué significa la complejidad O(sqrt(n)) u O(n^1/3)?

La notación O (Big O) describe el rendimiento o la complejidad de un algoritmo. O(sqrt(n)) significa que el tiempo de ejecución del algoritmo crece proporcionalmente a la raíz cuadrada del tamaño de la entrada (n). O(n^1/3) significa que el tiempo de ejecución crece proporcionalmente a la raíz cúbica del tamaño de la entrada. Un crecimiento más lento (como n^1/3 en comparación con sqrt(n)) indica un algoritmo más eficiente para entradas grandes.

Conclusión

Contar los divisores de un número es un problema clásico en la teoría de números que tiene aplicaciones prácticas en la informática. Hemos explorado dos enfoques principales en C++: el método ingenuo, que es simple y directo pero con una complejidad temporal de O(sqrt(n)), y el método optimizado, que aprovecha el poder de la factorización prima y la Criba de Eratóstenes para lograr una impresionante complejidad de O(n^1/3) (después de la precomputación de la criba). La elección del método dependerá en gran medida del tamaño de los números con los que necesites trabajar y de los recursos computacionales disponibles. Comprender la base matemática de estos algoritmos, especialmente el teorema fundamental de la aritmética, es clave para apreciar su elegancia y eficiencia.

Si quieres conocer otros artículos parecidos a Contando Divisores: De lo Básico a lo Optimizado en C++ puedes visitar la categoría Matemáticas.