Números primos hasta n

Planteamiento

Dado un número entero n, debemos imprimir todos los números primos desde 1 hasta n, en orden creciente y separados por un espacio.

Un número primo es un número entero mayor que 1 que solamente tiene dos divisores positivos: 1 y él mismo.

Por ejemplo, si:

20

la salida debe ser:

2 3 5 7 11 13 17 19

Es importante recordar que 1 no es un número primo.

Solución 1: Comprobar todos los divisores

Una forma sencilla de resolver el problema es recorrer todos los números desde 2 hasta n y comprobar si cada uno es primo.

Para saber si un número x es primo, podemos intentar dividirlo entre todos los números desde 2 hasta x - 1.

Por ejemplo, para comprobar si 7 es primo:

7 % 2 != 0
7 % 3 != 0
7 % 4 != 0
7 % 5 != 0
7 % 6 != 0

Como ninguna división tiene residuo 0, sabemos que 7 es primo.

Código

#include <iostream>
using namespace std;

bool esPrimo(int x) {
    if (x < 2)
        return false;

    for (int i = 2; i < x; i++) {
        if (x % i == 0)
            return false;
    }

    return true;
}

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

    for (int i = 2; i <= n; i++) {
        if (esPrimo(i)) {
            cout << i << " ";
        }
    }

    return 0;
}

Complejidad

Para cada número podemos llegar a probar aproximadamente n posibles divisores, y hacemos esto para aproximadamente n números.

Por lo tanto, la complejidad es:

O(n²)

Esta solución es fácil de entender, pero puede ser lenta cuando n es grande.

Solución 2: Comprobar divisores hasta √x

Podemos mejorar la solución anterior.

Para determinar si un número x es primo, no necesitamos probar todos los números menores que x. Solamente necesitamos probar divisores hasta √x.

¿Por qué?

Si un número tiene dos factores, al menos uno de ellos debe ser menor o igual que su raíz cuadrada.

Por ejemplo:

36 = 6 × 6

y:

√36 = 6

Por lo tanto, para comprobar si 36 es primo basta con encontrar un divisor antes o hasta 6.

Código

#include <iostream>
using namespace std;

bool esPrimo(int x) {
    if (x < 2)
        return false;

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

    return true;
}

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

    for (int i = 2; i <= n; i++) {
        if (esPrimo(i)) {
            cout << i << " ";
        }
    }

    return 0;
}

¿Por qué usamos i * i <= x?

La condición:

i * i <= x

es equivalente a:

i <= √x

pero no necesitamos calcular la raíz cuadrada explícitamente.

Por ejemplo, para comprobar si 97 es primo, solamente necesitamos probar divisores hasta 9, porque:

√97 ≈ 9.84

Si ningún número entre 2 y 9 divide a 97, entonces 97 es primo.

Complejidad

Para cada número hacemos aproximadamente √n comprobaciones.

Como comprobamos todos los números hasta n, la complejidad es:

O(n√n)

Esta solución es considerablemente más rápida que la anterior.

Solución 3: Criba de Eratóstenes

Existe otra forma de resolver el problema que es especialmente útil cuando queremos encontrar todos los números primos hasta n.

La Criba de Eratóstenes funciona eliminando los números que sabemos que no son primos.

Primero suponemos que todos los números desde 2 hasta n son primos:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

Comenzamos con 2.

Sabemos que 2 es primo, así que todos sus múltiplos mayores que él no pueden ser primos:

4, 6, 8, 10, 12, 14, 16, ...

Después pasamos al siguiente número que todavía no hemos eliminado: 3.

3 es primo, por lo que eliminamos sus múltiplos:

6, 9, 12, 15, 18, ...

Continuamos de esta manera.

Al terminar, los números que no fueron eliminados son precisamente los números primos.

Código

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

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

    vector<bool> primo(n + 1, true);

    primo[0] = false;

    if (n >= 1)
        primo[1] = false;

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

    for (int i = 2; i <= n; i++) {
        if (primo[i]) {
            cout << i << " ";
        }
    }

    return 0;
}

¿Cómo funciona el código?

Creamos un arreglo:

vector<bool> primo(n + 1, true);

La posición i indica si i sigue siendo considerado primo.

Por ejemplo:

primo[2] = true
primo[3] = true
primo[4] = true
...

Después marcamos 0 y 1 como no primos:

primo[0] = false;
primo[1] = false;

Luego recorremos los posibles números primos:

for (int i = 2; i * i <= n; i++)

Si i todavía está marcado como primo:

if (primo[i])

eliminamos todos sus múltiplos:

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

¿Por qué empezamos en i * i?

Supongamos que estamos procesando i = 5.

Sus múltiplos son:

5 × 2 = 10
5 × 3 = 15
5 × 4 = 20
5 × 5 = 25
...

Los números 10, 15 y 20 ya tuvieron que ser eliminados anteriormente al procesar 2 y 3.

Por eso, el primer múltiplo que necesitamos eliminar es:

5 × 5 = 25

De ahí que utilicemos:

int j = i * i;

en lugar de:

int j = 2 * i;

¿Por qué solamente llegamos hasta √n?

Al igual que en la segunda solución, solamente necesitamos procesar valores de i hasta:

√n

porque cualquier número compuesto menor o igual que n tiene al menos un factor menor o igual que √n.

Por eso utilizamos:

i * i <= n

Complejidad

La Criba de Eratóstenes tiene una complejidad temporal de:

O(n log log n)

y utiliza:

O(n)

memoria.

Esto la hace mucho más eficiente para encontrar todos los números primos hasta un n grande.

Comparación de las soluciones

Conclusión

Hay varias maneras de resolver el problema.

La primera solución es la más sencilla, pero también la más lenta.

La segunda solución mejora bastante el rendimiento porque solamente busca divisores hasta la raíz cuadrada del número.

Finalmente, la Criba de Eratóstenes es una solución especializada para encontrar todos los números primos hasta n. Aunque utiliza más memoria, es considerablemente más eficiente cuando n es grande.

Para aprender el concepto de números primos, la segunda solución es una buena opción porque muestra directamente cómo comprobar si un número es primo. Para problemas donde n es grande y necesitamos obtener todos los primos, la Criba de Eratóstenes suele ser la opción adecuada.