Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Prueba de primalidad por división de prueba

Comprueba si un entero es primo probando posibles divisores solo hasta su raíz cuadrada. En C, la condición `d <= n / d` permite comprobar ese límite sin riesgo de desbordamiento al multiplicar.

Versión: C23; repository compiler flag, production runtime not attested

Sintaxis

for (int d = 3; d <= n / d; d += 2) { if (n % d == 0) return 0; }

La prueba de primalidad por división de prueba comprueba si n tiene algún divisor distinto de 1 y de n. Primero descarta n < 2, acepta n == 2 y descarta los demás números pares. Para los candidatos restantes, prueba solo valores impares de d, empezando por 3. Si n % d == 0, el número es compuesto. Si el bucle no encuentra ningún divisor, el número es primo.

Los divisores aparecen por pares: si n = a * b y ambos factores son mayores que 1, al menos uno de ellos no supera la raíz cuadrada de n. El límite es inclusivo: para 49, el bucle también debe probar 7.

Para comprobar el límite de los divisores sin desbordamiento, usa d <= n / d en lugar de d * d <= n. Si n y d son positivos, la división entera en C redondea el cociente hacia abajo, por lo que ambas condiciones son matemáticamente equivalentes. Sin embargo, la primera evita calcular un producto que podría superar el rango de int y provocar un comportamiento indefinido. En el peor caso, el algoritmo realiza O(√n) pruebas y usa O(1) de espacio adicional.

Ejemplos

#include <stdio.h>

static int is_prime(int n)
{
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;

    for (int d = 3; d <= n / d; d += 2) {
        if (n % d == 0) return 0;
    }
    return 1;
}

int main(void)
{
    const int values[] = {-7, 0, 1, 2, 4, 9, 29, 49};
    for (size_t i = 0; i < sizeof values / sizeof values[0]; ++i) {
        printf("%d: %d\n", values[i], is_prime(values[i]));
    }
    return 0;
}

Resultado

-7: 0
0: 0
1: 0
2: 1
4: 0
9: 0
29: 1
49: 0

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes