Números Primos y Criba de Eratóstenes

¿Qué es un número primo?

Un número primo es un número natural mayor que 1 que solo es divisible por 1 y por sí mismo. Los primeros números primos son:

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...$

Propiedades importantes

1. El número 2 es el único número primo par
2. Todo número mayor que 1 puede expresarse como producto de primos (Teorema Fundamental de la Aritmética)
3. Hay infinitos números primos

Verificar si un número es primo

Método básico (Fuerza Bruta)

La forma más simple es verificar si algún número entre 2 y $n-1$ divide a $n$:

bool esPrimo(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Complejidad: $O(n)$ - Muy lento para números grandes.

Método optimizado (hasta $\sqrt{n}$)

Si $n$ tiene un divisor mayor que $\sqrt{n}$, entonces necesariamente tiene un divisor menor que $\sqrt{n}$. Por lo tanto, solo necesitamos verificar hasta $\sqrt{n}$:

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

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

Complejidad: $O(\sqrt{n})$ - Mucho mejor!

💡 ¿Por qué funciona el truco de i += 6?

Todos los primos mayores que 3 tienen la forma $6k \pm 1$. Esto es porque:

• $6k$ es divisible por 6
• $6k + 2$ y $6k + 4$ son divisibles por 2
• $6k + 3$ es divisible por 3

Por lo tanto, solo necesitamos verificar números de la forma $6k - 1$ y $6k + 1$.

La Criba de Eratóstenes

Cuando necesitamos encontrar todos los primos hasta un límite $n$, verificar cada número individualmente es ineficiente. La Criba de Eratóstenes es un algoritmo elegante que resuelve este problema.

¿Cómo funciona?

1. Crear una lista de números del 2 al $n$
2. Empezar con el primer primo (2)
3. Marcar todos los múltiplos de ese primo como compuestos
4. Encontrar el siguiente número no marcado (es primo)
5. Repetir hasta llegar a $\sqrt{n}$

Visualización

Para encontrar primos hasta 30:

Inicial:  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Eliminar múltiplos de 2:
          2  3  X  5  X  7  X  9  X 11  X 13  X 15  X 17  X 19  X 21  X 23  X 25  X 27  X 29  X

Eliminar múltiplos de 3:
          2  3  X  5  X  7  X  X  X 11  X 13  X  X  X 17  X 19  X  X  X 23  X 25  X  X  X 29  X

Eliminar múltiplos de 5:
          2  3  X  5  X  7  X  X  X 11  X 13  X  X  X 17  X 19  X  X  X 23  X  X  X  X  X 29  X

Primos:   2  3     5     7        11    13          17    19          23                29

Implementación básica

#include <bits/stdc++.h>
using namespace std;

vector<bool> criba(int n) {
    vector<bool> esPrimo(n + 1, true);
    esPrimo[0] = esPrimo[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (esPrimo[i]) {
            // Marcar todos los múltiplos de i como compuestos
            for (int j = i * i; j <= n; j += i) {
                esPrimo[j] = false;
            }
        }
    }

    return esPrimo;
}

int main() {
    int n = 100;
    vector<bool> primos = criba(n);

    cout << "Primos hasta " << n << ":" << endl;
    for (int i = 2; i <= n; i++) {
        if (primos[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

Complejidad: $O(n \log \log n)$ - Muy eficiente!

💡 ¿Por qué empezamos desde i*i?

Cuando llegamos al primo $p$, todos los múltiplos menores que $p^2$ ya fueron marcados por primos anteriores:

• $2p$ fue marcado por 2
• $3p$ fue marcado por 3
• ...
• $(p-1)p$ fue marcado por algún primo menor

Por eso empezamos desde $p^2$.

Implementación optimizada (guardando los primos)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e7;
vector<bool> esPrimo(MAXN + 1, true);
vector<int> primos;

void generarPrimos() {
    esPrimo[0] = esPrimo[1] = false;

    for (int i = 2; i <= MAXN; i++) {
        if (esPrimo[i]) {
            primos.push_back(i);
            if ((long long)i * i <= MAXN) {
                for (int j = i * i; j <= MAXN; j += i) {
                    esPrimo[j] = false;
                }
            }
        }
    }
}

int main() {
    generarPrimos();

    cout << "Cantidad de primos hasta " << MAXN << ": " << primos.size() << endl;
    cout << "Primeros 10 primos: ";
    for (int i = 0; i < 10 && i < primos.size(); i++) {
        cout << primos[i] << " ";
    }
    cout << endl;

    // Verificar si un número es primo en O(1)
    int n = 997;
    if (esPrimo[n]) {
        cout << n << " es primo" << endl;
    }

    return 0;
}

Criba Segmentada

Para números muy grandes (hasta $10^{12}$), no podemos crear un arreglo tan grande. La criba segmentada divide el rango en bloques:

#include <bits/stdc++.h>
using namespace std;

vector<int> cribaSimple(int limite) {
    vector<bool> esPrimo(limite + 1, true);
    vector<int> primos;

    for (int i = 2; i <= limite; i++) {
        if (esPrimo[i]) {
            primos.push_back(i);
            for (long long j = (long long)i * i; j <= limite; j += i) {
                esPrimo[j] = false;
            }
        }
    }
    return primos;
}

// Cuenta primos en el rango [L, R]
long long contarPrimosEnRango(long long L, long long R) {
    // Generar primos hasta sqrt(R)
    int limite = sqrt(R) + 1;
    vector<int> primos = cribaSimple(limite);

    // Criba para el rango [L, R]
    vector<bool> esPrimo(R - L + 1, true);

    for (int p : primos) {
        // Encontrar el primer múltiplo de p >= L
        long long inicio = max((long long)p * p, ((L + p - 1) / p) * p);

        for (long long j = inicio; j <= R; j += p) {
            esPrimo[j - L] = false;
        }
    }

    // Caso especial: 0 y 1 no son primos
    if (L == 0) esPrimo[0] = false;
    if (L <= 1) esPrimo[1 - L] = false;

    long long cuenta = 0;
    for (int i = 0; i <= R - L; i++) {
        if (esPrimo[i]) cuenta++;
    }

    return cuenta;
}

int main() {
    long long L = 1000000000, R = 1000001000;
    cout << "Primos en [" << L << ", " << R << "]: " << contarPrimosEnRango(L, R) << endl;
    return 0;
}

Problemas de práctica

Problema 1: Contar primos

Dado $n$, cuenta cuántos primos hay menores o iguales a $n$.

#include <bits/stdc++.h>
using namespace std;

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

    vector<bool> 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 cuenta = 0;
    for (int i = 2; i <= n; i++) {
        if (esPrimo[i]) cuenta++;
    }

    cout << cuenta << endl;
    return 0;
}

Problema 2: Suma de primos

Calcula la suma de todos los primos hasta $n$.

#include <bits/stdc++.h>
using namespace std;

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

    vector<bool> 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;
            }
        }
    }

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

    cout << suma << endl;
    return 0;
}

Problema 3: Conjetura de Goldbach

La conjetura de Goldbach dice que todo número par mayor que 2 puede expresarse como suma de dos primos. Dado un número par $n$, encuentra dos primos que sumen $n$.

#include <bits/stdc++.h>
using namespace std;

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

    vector<bool> 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;
            }
        }
    }

    for (int i = 2; i <= n / 2; i++) {
        if (esPrimo[i] && esPrimo[n - i]) {
            cout << i << " + " << (n - i) << " = " << n << endl;
            break;
        }
    }

    return 0;
}

Resumen

Ejercicios recomendados

1. SPOJ - PRIME1 - Prime Generator
2. Codeforces - Almost Prime
3. UVa - Goldbach's Conjecture