Números Primos

¿Qué es un número primo?

Un número primo es un número mayor que 1 que solo es divisible entre 1 y sí mismo. Piénsalo como un átomo: no se puede descomponer en factores más pequeños.

• Primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
• No primos (compuestos): 4=2×2, 6=2×3, 9=3×3, 12=2×2×3, …
• Casos especiales: 1 no es primo ni compuesto. 2 es el único primo par.

Verificar si un número es primo

Método básico: $O(\sqrt{n})$

bool esPrimo(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

¿Por qué solo hasta $\sqrt{n}$? Si n = a × b, al menos uno de los dos factores es ≤ $\sqrt{n}$. Así que si no encontramos divisores hasta ahí, no hay.

¿Por qué saltar los pares? Si n no es divisible entre 2, tampoco lo será entre 4, 6, 8… Así revisamos la mitad de candidatos.

La Criba de Eratóstenes

Cuando necesitas todos los primos hasta N, no verificas uno por uno. Usas la criba: "tacha todos los múltiplos de cada primo".

Analogía: Imagina que tienes boletos numerados del 2 al N en una mesa. Tomas el 2 (primo) y tachas todos sus múltiplos (4, 6, 8…). Luego tomas el 3 (primo, no tachado) y tachas sus múltiplos (6, 9, 12…). Repites. Los que quedan sin tachar son primos.

const int MAXN = 10000005;
bool esPrimo[MAXN];

void criba(int n) {
    fill(esPrimo, esPrimo + n + 1, true);
    esPrimo[0] = esPrimo[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (esPrimo[i]) {
            for (int j = i * i; j <= n; j += i) {
                esPrimo[j] = false;
            }
        }
    }
}

Detalle: Empezamos a tachar desde i*i porque los múltiplos menores ya fueron tachados por primos más pequeños.

Complejidad: $O(n \log \log n)$ — ¡casi lineal!

Ejemplo

Criba hasta 20:

Inicio: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
i=2:    2 3 . 5 . 7 . 9 .  11 .  13 .  15 .  17 .  19 .
i=3:    2 3   5   7   .     11    13    .      17    19
Primos: 2 3 5 7 11 13 17 19

Contar primos hasta N

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

    criba(n);

    int cuenta = 0;
    for (int i = 2; i <= n; i++) {
        if (esPrimo[i]) cuenta++;
    }

    cout << "Hay " << cuenta << " primos hasta " << n << endl;
    return 0;
}

Menor factor primo (SPF)

Variante útil de la criba: para cada número, guardar su menor factor primo:

int spf[MAXN];  // smallest prime factor

void cribaSpf(int n) {
    for (int i = 0; i <= n; i++) spf[i] = i;

    for (int i = 2; i * i <= n; i++) {
        if (spf[i] == i) {  // i es primo
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

Con esto puedes factorizar cualquier número en $O(\log n)$:

vector<int> factorizar(int n) {
    vector<int> factores;
    while (n > 1) {
        factores.push_back(spf[n]);
        n /= spf[n];
    }
    return factores;
}
// factorizar(60) → {2, 2, 3, 5}

Ejercicio de práctica

Dado un rango [A, B], imprime todos los números primos en ese rango.

Entrada: 10 30 Salida: 11 13 17 19 23 29

#include <iostream>
using namespace std;

const int MAXN = 1000005;
bool esPrimo[MAXN];

void criba(int n) {
    fill(esPrimo, esPrimo + n + 1, true);
    esPrimo[0] = esPrimo[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (esPrimo[i]) {
            for (int j = i * i; j <= n; j += i) {
                esPrimo[j] = false;
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    criba(b);

    for (int i = a; i <= b; i++) {
        if (esPrimo[i]) cout << i << " ";
    }
    cout << endl;

    return 0;
}