Implementar el Criba de Eratóstenes en C

Introducción

En este laboratorio, aprenderá a implementar el algoritmo del Criba de Eratóstenes en C para encontrar números primos hasta un límite superior dado. Comenzará leyendo el límite superior del usuario, luego marcará los múltiplos de los números primos como no primos y, finalmente, imprimirá todos los números primos encontrados. Este laboratorio aborda conceptos de teoría de números y matemáticas discretas utilizando el lenguaje de programación C.

El laboratorio consta de tres pasos principales: leer el límite superior, marcar los múltiplos como no primos e imprimir todos los números primos. Siguiendo estos pasos, obtendrá una comprensión más profunda del algoritmo del Criba de Eratóstenes y su implementación en C.

Skills Graph

Leer el límite superior

En este paso, aprenderá a leer el límite superior para el algoritmo del Criba de Eratóstenes en C. El límite superior determina el rango de números primos que queremos encontrar.

Primero, creemos un nuevo archivo C para nuestra implementación:

cd ~/project
nano prime_sieve.c

Ahora, escribamos el código inicial para leer el límite superior:

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    printf("Upper limit entered: %d\n", upper_limit);

    return 0;
}

Compile y ejecute el programa:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Salida de ejemplo:

Enter the upper limit for finding prime numbers: 50
Upper limit entered: 50

Analicemos el código:

• Usamos scanf() para leer una entrada entera del usuario
• El especificador de formato %d le dice a scanf() que lea un entero
• Guardamos la entrada en la variable upper_limit
• Luego imprimimos el límite superior ingresado para confirmar la entrada

Marcar múltiplos como no primos

En este paso, implementará la lógica central del algoritmo del Criba de Eratóstenes para marcar los múltiplos de los números primos como no primos.

Modifiquemos el archivo prime_sieve.c anterior:

cd ~/project
nano prime_sieve.c

Actualice el código para incluir una matriz y marcar múltiplos:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // Cree una matriz booleana para marcar números primos y no primos
    bool is_prime[upper_limit + 1];

    // Inicialice todos los números como primos
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Marque los múltiplos de cada número primo como no primo
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Marque los múltiplos de p como no primos
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("Marcar múltiplos completado.\n");

    return 0;
}

Compile y ejecute el programa:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Salida de ejemplo:

Enter the upper limit for finding prime numbers: 50
Marcar múltiplos completado.

Analicemos la lógica del Criba de Eratóstenes:

• Creamos una matriz booleana is_prime para rastrear números primos y no primos
• Inicialmente, todos los números se marcan como primos
• Iteramos a través de los números de 2 a la raíz cuadrada (sqrt) del límite superior
• Para cada número primo, marcamos sus múltiplos como no primos
• Comenzamos a marcar a partir de p^2 para optimizar el algoritmo
• El bucle interno incrementa en p para marcar todos los múltiplos de p

Imprimir todos los números primos

En este paso, completará la implementación del Criba de Eratóstenes imprimiendo todos los números primos encontrados en el rango dado.

Modifiquemos el archivo prime_sieve.c para agregar la funcionalidad de impresión:

cd ~/project
nano prime_sieve.c

Actualice el código para imprimir números primos:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("Enter the upper limit for finding prime numbers: ");
    scanf("%d", &upper_limit);

    // Cree una matriz booleana para marcar números primos y no primos
    bool is_prime[upper_limit + 1];

    // Inicialice todos los números como primos
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Marque los múltiplos de cada número primo como no primo
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Marque los múltiplos de p como no primos
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // Imprima todos los números primos
    printf("Prime numbers up to %d are:\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

Compile y ejecute el programa:

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Salida de ejemplo:

Enter the upper limit for finding prime numbers: 50
Prime numbers up to 50 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Analicemos los pasos finales:

• Después de marcar los múltiplos, iteramos a través de la matriz is_prime
• Imprimimos solo los números que permanecen marcados como primos
• La salida muestra todos los números primos hasta el límite especificado por el usuario

Resumen

En este laboratorio, primero aprendió a leer el límite superior para el algoritmo del Criba de Eratóstenes en C. Creó un archivo C, prime_sieve.c, y escribió código para solicitar al usuario el límite superior y almacenarlo en la variable upper_limit. Luego, implementó la lógica central del algoritmo del Criba de Eratóstenes creando una matriz booleana para marcar números primos y no primos. Inicializó todos los números como primos y luego marcó los múltiplos de cada número primo como no primos. Finalmente, aprenderá a imprimir todos los números primos dentro del límite superior dado.