Algoritmos numéricos

Divisores y primos

Divisiones de prueba

Un entero $n \geq 2$ es primo si sus únicos divisores positivos son 1 y $n$; si tiene otro, es compuesto; 0 y 1 no son ni lo uno ni lo otro. La definición sugiere de inmediato un algoritmo: probar cada candidato $d$ entre 2 y $n - 1$ y declarar compuesto el número en cuanto uno divida. Es el bucle del menor divisor de la clase Bucles, y es correcto. Ahora bien, para un primo de diez cifras hace casi diez mil millones de divisiones, y casi todas son inútiles, por la razón siguiente.

De ello se sigue que el número de divisiones baja de unas $n$ a unas $\sqrt{n}$: para $n$ cercano a dos mil millones, de dos mil millones a cuarenta y seis mil. El programa usa el patrón de la bandera de la clase Diseñar bucles correctos: isPrime empieza verdadera y el bucle la apaga si encuentra un divisor.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{} es primo", n);    } else {        std::println("{} no es primo", n);    }}

2147483647

2147483647 es primo

Tres decisiones merecen comentario. La bandera se inicializa con n >= 2, de modo que 0, 1 y los negativos se declaran no primos sin entrar al bucle: olvidar ese caso es el error típico, porque con $n = 1$ el bucle no da ninguna vuelta y el programa declararía primo al 1. La condición del for tiene dos partes: la bandera, que detiene el bucle en el primer divisor, y el límite. Y el límite está escrito d <= n / d, que, para enteros positivos, equivale a $d^2 \leq n$ (la división entera trunca, pero $d$ no supera al cociente truncado exactamente cuando no supera a $n/d$, porque $d$ es entero). El número de la entrada, $2^{31} - 1$, es el mayor int y es primo; el programa lo decide con $46\,339$ divisiones.

El invariante del bucle es: ningún entero de 2 a $d - 1$ divide a $n$, mientras la bandera siga verdadera. Vale al entrar, cuando el intervalo de 2 a 1 está vacío; se conserva, porque si $d$ no divide a $n$ el intervalo crece en un número que no divide; y al salir con la bandera verdadera, el invariante y la condición falsa, $d^2 > n$, dicen juntos que ningún candidato hasta $\sqrt{n}$ divide a $n$, que es lo que la proposición exige. La variante es la cantidad de candidatos que faltan por probar, es decir, de enteros entre $d$ y $\sqrt{n}$: decrece en uno por vuelta y no baja de cero.

La condición que desborda

La manera natural de escribir el límite es d * d <= n, y es un error. Con la entrada anterior, el bucle llega a $d = 46\,341$, y entonces el producto $46\,341^2 = 2\,147\,488\,281$ supera el máximo de int.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("¿Primo? {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

El detector de comportamiento indefinido detiene el programa en el producto. Sin él, el desbordamiento con signo es comportamiento indefinido, y la norma no dice qué ocurre. Lo que se observa con GCC en Linux, con y sin optimización, es instructivo: el producto da la vuelta y resulta negativo o menor que $n$, y como ningún int supera al máximo, la condición d * d <= n ya no deja de cumplirse; el bucle sigue probando candidatos durante unos dos mil millones de vueltas, hasta llegar a $d = n$, que divide a $n$, y el programa declara compuesto a un número primo. Un error de desbordamiento no se manifiesta como un desbordamiento, sino como una respuesta falsa. La forma d <= n / d no puede desbordar, porque divide en lugar de multiplicar; la clase Bits y biblioteca matemática ofrecía otra salida, calcular el límite una vez con std::sqrt, pero entonces la exactitud del límite depende del redondeo de la coma flotante, y la división entera no tiene ese problema.

La clase «Números primos y el teorema fundamental de la aritmética», del curso Álgebra y Geometría I, demuestra que todo entero mayor que 1 es producto de primos de una sola manera; las divisiones de prueba son la manera más directa de encontrar ese producto, dividiendo $n$ por cada divisor hallado y siguiendo con el cociente.