---
tags: number-theory, prime-numbers, divisors, primality-test
---

# Divisores y números primos
En la sección pasada vimos el concepto de divisibilidad, ahora revisaremos algunas propiedades que nos permitirán obtener los divisores de un número de forma eficiente, así como las "unidades" fundamentales de la aritmética: los números primos.

## Divisores de un entero
Sea $n \in \mathbb{N}$, vamos a obtener todos sus divisores positivos. Sabemos que si alguna $d$ divide a $n$, se cumple que $n=dk$ para alguna $k \in \mathbb{N}$. Esto implica que $1 \leq d \leq n$, es decir, ningún divisor de $n$ será mayor a $n$, por lo que podemos limitar nuestro espacio de búsqueda.

:::spoiler **Demostración**
$$
\begin{align}
k &\geq 1 \\
kd &\geq d \\
n &\geq d \\
d &\leq n
\end{align}
$$
:::

:::info
:information_source: **Ejemplo:** los divisores de $n=12$ son $\{1,2,3,4,6,12\}$.
:::

Por lo tanto, un primer algoritmo para obtener todos los divisores de $n$ es iterar para todas las $d$ entre $1$ y $n$, y quedarnos solo con las que dejen un residuo de $0$ con $n$, es decir, `n % d = 0`:

### Algoritmo 1: obtener divisores con fuerza bruta

vector<int> getDivisors(int n){
    vector<int> divisors;
    for(int d = 1; d <= n; d++){
        if(n % d == 0){
            divisors.push_back(d);
        }
    }
    return divisors;
}

El algoritmo anterior tiene una complejidad de $O(n)$, pues revisamos cada candidato a divisor entre $1$ y $n$ una vez, y vemos que siempre nos devuelve los divisores ordenados de menor a mayor.

Podemos mejorar la complejidad con la siguiente observación: para cualquier $n$, podemos reacomodar sus divisores en parejas $(a, b)$ tales que $ab=n$ y $a \leq b$.

:::info
:information_source: **Ejemplo:** para $n=12$, podemos formar las parejas como:
- $(1, 12)$
- $(2, 6)$
- $(3, 4)$
:::

Es decir, si conocemos el elemento más pequeño de la pareja $a$, podemos conocer $b$ simplemente despejando: $b=\frac{n}{a}$. Por lo tanto, podemos iterar sobre todas las $a$'s posibles y hallar $b$ para cada una. La pregunta es, ¿hasta qué valor puede llegar $a$?

:::spoiler **Demostración**
Sabemos que $a \leq b$, si multiplicamos ambos lados por $a$ obtenemos $a^2 \leq ab$, pero $ab=n$, por lo tanto $a^2 \leq n$.
:::

Por lo tanto, $a \leq \lfloor \sqrt{n} \rfloor$, y nuestro espacio de búsqueda se redujo considerablemente. Entonces, ya estamos listos para proponer el siguiente algoritmo:

### Algoritmo 2: obtener divisores de forma optimizada

vector<int> getDivisors(int n){
	vector<int> divisors;
	for(int a = 1; a*a <= n; a++){ // Se recomienda usar a*a<=n en lugar de a<=sqrt(n) por la precisión
		if(n % a == 0){
			int b = n / a;
			divisors.push_back(a);
			divisors.push_back(b);
		}
	}
	return divisors;
}

La complejidad ahora queda como $O(\sqrt{n})$, lo cual lo hace viable para $n \leq 10^{14}$. Sin embargo, el algoritmo tiene un ligero fallo:

:::warning
:warning: Cuando $n$ es un cuadrado perfecto, existirá algún divisor $a$ tal que $a^2=n$, es decir, $(a, a)$ es una pareja. El algoritmo anterior va a meter a la lista de divisores el valor de $a$ dos veces, pues $a=b$. La solución es simple, solo hay que verificar que $a \neq b$ en la línea 7:

if(a != b) divisors.push_back(b);

:::

Además, ahora no obtenemos los divisores en orden ascendente, pero para muchos problemas el orden no va a importar. Si los deseamos ordenados, solo agregamos `sort(divisors.begin(), divisors.end());` antes de retornar el arreglo.

## Números primos
Los números primos son fundamentales en teoría de números, pues son los números más elementales, a partir de los cuáles podemos construir los demás.

Un número entero $p$ es **primo** si:
- $p$ es positivo y $p \geq 2$
- Los únicos divisores de $p$ son $1$ y $p$

Los primeros números primos son: $2, 3, 5, 7, 11, 13, 17, 23, \ldots$

Si un número positivo $n \geq 2$ no es primo, decimos que es **compuesto**. Los primeros números compuestos son: $4, 6, 8, 9, 10, 12, 14, 15, \ldots$

Notemos que el $1$ no es primo ni compuesto, simplemente le podemos llamar *la unidad*.

La pregunta natural es ahora, dado un entero positivo $n$, ¿cómo sabemos si es primo o compuesto? Usando la definción podemos proponer un algoritmo sencillo: verificar que el número de divisores de $n$ sea exactamente igual a 2:

### Algoritmo 3: test de primalidad básico

bool isPrime(int n){
	int nDivs = 0;
	for(int d = 1; d <= n; d++){
		if(n % d == 0){
			nDivs++;
		}
	}
	return nDivs == 2;
}

La complejidad es $O(n)$. Podemos optimizarlo de la siguiente manera: sabemos que el $1$ y $n$ siempre van a dividir a $n$ (a estos los llamaremos los *divisores triviales de $n$*), por lo tanto, en el momento que encontremos un divisor entre $2$ y $n-1$ (a estos los llamaremos los divisores *no triviales*), ya sabremos que $n$ es un número compuesto y podemos retornar `false` desde ahí:

### Algoritmo 4: test de primalidad optimizado para números compuestos

bool isPrime(int n){
    if(n == 1) return false; // El 1 es un caso especial
    for(int d = 2; d <= n-1; d++){
        if(n % d == 0){
            return false; // Encontramos un divisor de n que no es ni 1 ni n
        }
    }
    return true; // Si llegamos hasta este punto, n tiene que ser primo
}

Vemos que para los números compuestos el algoritmo retornará antes, pero para los números primos tenemos el peor caso pues tenemos que checar todos los candidatos a divisores, por lo tanto, este algoritmo sigue siendo $O(n)$.

Una optimización más es usar la propiedad de las parejas: si $n=ab$ y $a \leq b$, sabemos que $a \leq \lfloor \sqrt{n} \rfloor$, entonces podemos buscar los divisores no triviales de $n$ solo en el rango $[2, \lfloor \sqrt{n} \rfloor]$, teniendo el siguiente algoritmo:

### Algoritmo 5: test de primalidad optimizado

bool isPrime(int n){
    if(n == 1) return false; // El 1 sigue siendo un caso especial
    for(int d = 2; d*d <= n; d++){
        if(n % d == 0){
            return false; // Encontramos un divisor de n que no es ni 1 ni n
        }
    }
    return true; // Si llegamos hasta este punto, n tiene que ser primo
}

Ahora la complejidad es $O(\sqrt{n})$ para cualquier caso, sin importar si $n$ es primo o compuesto.

Por último, una optimización más es la siguiente: todos los números pares mayores a $2$ son compuestos, pues el $2$ los divide. Entonces, podemos hacer ese chequeo al principio, y después, solo verificar los divisores impares: eso implicaría modificar la línea 3 por: `for(int d = 3; d*d <= n; d += 2)`. Se queda como ejercicio la implementación completa.

:::warning
:warning: Hay que tener mucho cuidado con los algoritmos anteriores cuando la $n$ exceda el valor máximo permitido en un `int`, pues hacemos multiplicaciones y se pueden desbordar, ocasionando que posiblemente el algoritmo se cicle. Usualmente la regla es: si $n > 10^9$, usemos `long long int`.
:::