Comprobar si un número es primo

En esta lección aprenderás un algoritmo para comprobar si un número es primo, y entenderás una forma eficiente de hacerlo. Está dirigida a quien busca «comprobar números primos en JavaScript» o «algoritmo de números primos».

Que un número sea primo (divisible solo entre 1 y él mismo) se determina comprobando si es divisible por algún número desde el 2 hasta «la raíz cuadrada de ese número». Si ninguno lo divide exactamente, es primo. La idea clave es que cortar la comprobación en la raíz cuadrada, en vez de probar todos los números uno a uno, reduce drásticamente el cálculo.

El código de ejemplo recorre en la práctica solo «hasta la raíz cuadrada» usando la condición i * i <= n. Escribirlo así, en lugar de usar Math.sqrt(), es un algoritmo un punto más astuto que además se ahorra el coste de la propia raíz. Prueba a comparar los resultados de dos números, 17 y 18.

Un tropiezo habitual al empezar es el razonamiento de por qué basta comprobar hasta la raíz cuadrada. En cualquier pareja de números que divide exactamente a otro, uno queda en o por debajo de la raíz y el otro en o por encima, así que basta revisar el rango inferior: esa es la propiedad en la que se apoya el algoritmo. Pensar cómo comprobar algo con eficiencia es una práctica estupenda de fundamentos.

Es una propiedad matemática importante que se usa también en la base de la criptografía, y diseñar un algoritmo de comprobación eficiente es uno de los básicos de la informática. Tecnologías de cifrado como RSA, que protegen las comunicaciones de internet, se apoyan en cálculos con primos enormes como técnica central.