¡Explicación completa de la detección de primos en C! Prueba de división, criba de Eratóstenes y optimización

1. Introducción

2. ¿Qué es un número primo?

2.1. Características básicas de los números primos

• El menor número primo es 2 (el único número primo par)
• 1 no es un número primo (porque solo tiene un divisor)
• Existen infinitos números primos
• Si un entero n mayor o igual a 2 no es primo, entonces es divisible por un primo mayor o igual a 2

2.2. Ejemplos concretos de números primos

3. Método básico para determinar números primos en C (🔰 Para principiantes)

3.1. Método de prueba de división (básico)

• Si N es un entero mayor o igual a 2, verificar si es divisible por números desde 2 hasta N-1
• Si hay un número que divide exactamente, es un «número compuesto»; si no, es un «número primo»

#include 

int is_prime(int n) {
    if (n < 2) return 0;  // Los números menores o iguales a 1 no son primos
    for (int i = 2; i < n; i++) {  // Verificar si es divisible desde 2 hasta n-1
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num = 7;
    if (is_prime(num))
        printf("%d es un número primon", num);
    else
        printf("%d no es un número primon", num);
    return 0;
}

7 es un número primo

4. Método eficiente para determinar números primos en C [Criba de Eratóstenes – Versión mejorada del método de prueba de división]

1. Método de prueba de división hasta √N (optimizado)
2. Criba de Eratóstenes (sieve)

4.1. Método de prueba de división hasta √N (optimizado)

#include 
#include 

int is_prime_optimized(int n) {
    if (n < 2) return 0;
    if (n % 2 == 0 && n != 2) return 0;  // Los números pares no son primos excepto 2
    for (int i = 3; i <= sqrt(n); i += 2) {  // Solo verificar números impares (saltar pares)
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num = 29;
    if (is_prime_optimized(num))
        printf("%d es un número primo\n", num);
    else
        printf("%d no es un número primo\n", num);
    return 0;
}

29 es un número primo

4.2. Criba de Eratóstenes (sieve)

• Comenzar con 2 y eliminar todos sus múltiplos
• Luego, eliminar los múltiplos del número mínimo restante (3)
• Repitiendo esto, solo quedan los números primos

#include 
#include 

void sieve(int n) {
    bool prime[n + 1];
    for (int i = 0; i <= n; i++) prime[i] = true;

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

    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d ", p);
    printf("\n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

5. Comparación de rendimiento de algoritmos de determinación de números primos en C [Medición de velocidad y optimización]

• Método de prueba de división (básico): O(N)
• Prueba de división hasta √N (optimizado): O(√N)
• Criba de Eratóstenes (para encontrar primos en un rango): O(N log log N)

5.1. Método de medición del tiempo de ejecución

#include 
#include 

void measure_time(void (*func)(int), int n) {
    clock_t start, end;
    start = clock();  // Inicio de medición

    func(n);  // Ejecutar la función objetivo de medición

    end = clock();  // Fin de medición
    printf("Execution time: %lf secondsn", (double)(end - start) / CLOCKS_PER_SEC);
}

5.2. Medición del tiempo de ejecución de cada método

5.2.1. Método de prueba de división (O(N))

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

void test_trial_division(int limit) {
    int count = 0;
    for (int i = 2; i <= limit; i++) {
        if (is_prime(i)) count++;
    }
    printf("Total primes: %dn", count);
}

5.3. Comparación del tiempo de ejecución (graficado)

6. Preguntas frecuentes (FAQ)

Q1: ¿Por qué se usa la raíz cuadrada en la determinación de números primos?

• 1 × 49
• 7 × 7 (raíz cuadrada)
• 49 × 1

Q2: ¿En qué situaciones se debe usar el tamiz de Eratóstenes?

• Quiero listar los números primos desde 1 hasta 1 millón
• Quiero realizar la determinación de primos para múltiples números de manera eficiente

Q3: ¿La velocidad de la determinación de primos cambia según el entorno de C?

• Tipo de compilador (GCC, Clang, MSVC, etc.)
• Opciones de optimización durante la compilación
• Rendimiento de la CPU (especialmente afecta la velocidad del procesamiento de bucles)

gcc -O3 prime.c -o prime

7. Resumen y direcciones de aprendizaje futuras

7.1. Resumen general del artículo

🔹 ¿Qué es un número primo?

• número natural que no tiene divisores aparte de 1 y él mismo
• Si verificamos hasta la raíz cuadrada, podemos reducir cálculos innecesarios (complejidad O(√N))

🔹 Métodos de determinación de números primos en C

🔹 Selección del algoritmo óptimo

7.2. Direcciones para el aprendizaje futuro

1️⃣ Algoritmos de determinación de primos más avanzados

• Método de determinación de primos Miller-Rabin (probabilístico)
• Método de determinación de primos AKS (determinístico)

2️⃣ Técnicas de optimización en C

• Opciones de optimización del compilador (-O2, -O3)
• Procesamiento paralelo utilizando multihilo

3️⃣ Manejo de números grandes en C

• Usar la biblioteca GMP (GNU Multiple Precision)

7.3. Ideas de proyectos prácticos

7.4. Resumen

• El método de prueba de división (básico) tiene una complejidad de O(N) y es lento, por lo que no es adecuado para números grandes.
• El método de prueba de división √N tiene O(√N) y es adecuado para la determinación individual de números grandes.
• La criba de Eratóstenes tiene O(N log log N) y permite obtener listas de primos rápidamente.
• ¡Es importante seleccionar el algoritmo óptimo según el uso!