Un algoritmo de un día : Cómo comprobar si un número primo en JavaScript

Marina Semes
Marina Semes

Seguir

el 28 de Mayo de 2020 · 7 min read

es casi garantizado que en algún momento de su codificación de la educación se le pedirá que escriba algún tipo de función que consiste en números primos. Es un ejercicio popular en los campos de entrenamiento de codificación y, a veces, incluso aparece en las entrevistas de trabajo.

¿Qué son los números primos?

Un número primo es un número natural mayor que 1 cuyos únicos factores son 1 y el número en sí. Es decir, solo se puede dividir por igual entre 1 y sí mismo.

Los números naturales son enteros positivos como 1, 5, 201, 229999, etc. El número 0, fracciones, decimales y números negativos no son números naturales.

El número 5 es un número primo porque sus ÚNICOS factores son 1 y 5. No hay otra manera de «crear» el número 5.

El número 4 no es un número primo porque 2 x 2 también nos da 4.

El número 20 no es un número primo porque 5 x 4 también nos da 20, así como 2 x 10.

Los números primos nunca son pares (excepto 2)

Una de las formas más rápidas de verificar si un número es un número primo o no es verificar si es un número par. Si un número se puede dividir por 2 sin dejar un resto, ya no cumple con la definición de un número primo, un número que solo se puede dividir a partes iguales por 1 y por sí mismo.

En JavaScript podemos comprobar si hay números pares utilizando el operador de módulo (%).

El operador de módulo devuelve el resto después de que un entero se divide por otro.
Por ejemplo, 12% 5 devuelve 2.
Y 59% 5 devuelve 4.

Si divide un entero por 2 y el resto es 0, sabemos que el entero es un número par.

Por ejemplo 10 % 2 = 0
Y 2200 % 2 = 0

en JavaScript se verá algo como esto:
num % 2 === 0

Así que comencemos a crear nuestra función JavaScript para verificar si un número es un número primo o no:

function isPrime(num) {
if (num % 2 === 0) { return false;
} return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer

Recuerde que 2 ES un número primo

La función anterior, sin embargo, también indicará que 2 no es un número primo, por lo que tendremos que reescribir nuestra función. También podemos ocuparnos de otros enteros que no sean números enteros, como 0 y números negativos.

function isPrime(num) {
if (num === 2) return true;
if (num <= 1) return false; if (num % 2 === 0) {
return false;
}
return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer

La palabra clave ‘return’ indica una salida de la función cuando se encuentra con una instrucción que es verdadera. Si el número es 2, la función deja de ejecutarse en la segunda línea:

if (num === 2) return true;

Puede encontrar una gran lista de números primos conocidos aquí para ayudarlo a verificar la función.
No todos los números desiguales son números primos

Esta función funciona bien para verificar si un número es par o no, pero falla con números desiguales como 9 y 27 que no son números primos.

Vamos a tener que comprobar si el parámetro se puede dividir en otros factores (a excepción de 1, en sí mismo y 2) sin dejar un resto. El número 9, por ejemplo, también se puede dividir por 3.

Hacemos esto haciendo uso de un bucle for donde en cada iteración, el parámetro se divide por otra variable de bucle. El bucle se sigue ejecutando hasta que no haya restos o no haya más variables de bucle disponibles.

function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true; for (let i= 2; i < num; i++) { //we start with 2 to weed out the even numbers if (num % i === 0) {
return false;
}
} return true;
}//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False

La función mantiene el bucle y la comprobación de restos. En cada iteración, el argumento se divide por una nueva variable de bucle y el resto se comprueba. Si el resto es 0, significa que el argumento es completamente divisible por otro número que no sea él mismo y no es un número primo.

Nota al margen: ¿Cuál es la diferencia entre un parámetro y un argumento?
Los parámetros son las variables utilizadas como parte de la definición de la función. Por ejemplo, el num en la función isPrime (num) es el parámetro.Los argumentos

son los valores pasados a la función cuando se invoca. Por ejemplo
el número 9 en isPrime(9) es el argumento.

Si hay un resto, la función itera de nuevo hasta que alcanza el límite en

 i < num

Cuando se alcanza la iteración final y aún queda un resto, el argumento es un número primo y la función se detiene.
Terminamos con una variable de bucle que es un número más pequeño que el parámetro porque no estamos interesados en factores que son más grandes que el argumento.

Una demostración rápida

Demostremos esto con el número primo de 5.

function isPrime(num) {
if (num <= 1) return false;
//5 is larger than 1, so we continue with the function if (num === 2) return true;
//5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;}

Primer bucle:
1. i = 2 y 2 < 5, así que continuamos con el bucle
2. 5% 2 da un resto para que no salgamos del bucle, sino que continuemos con i++

Segundo bucle:
1. i = 3 y 3 < 5, así que continuamos con el bucle
2. 5% 3 da un resto para que no salgamos del bucle, sino que continuemos con i++

Tercer bucle:
1. i = 4 y 4 < 5, y hemos llegado al final del bucle, porque 5 no es < de 5
2. el 5% 4 da un resto. Esto significa que el número 5 es un número primo

Usando raíces cuadradas con números primos más grandes

Los números primos se escalan rápidamente en números enormes. Esto significa que nuestro bucle for sigue iterando de la variable de un bucle a la siguiente varias veces.

Podemos acortar el proceso usando la raíz cuadrada de un parámetro. Una raíz cuadrada de un entero es el número que se multiplicó por sí mismo para crear un producto.

La raíz cuadrada de 81 es 9 porque 9 x 9 = 81.

En lugar de iterar de 2 a 80 para verificar si quedan restos o no, podemos iterar hasta e incluyendo 9, la raíz cuadrada de 81.
9% 9 = 0, lo que significa que 81 no es un número primo.
Esto tiene sentido porque 9 x 9 son factores de 81, lo que significa que no cumple con la definición de un número primo, un número que solo se puede dividir a partes iguales por sí mismo y 1.

En JavaScript, puede encontrar la raíz cuadrada de un número usando Matemáticas.Plaza. Lo escribimos así:

Math.sqrt(num);

Usémoslo en nuestra función que comprueba si un número es un número primo:

function isPrime(num) {
if (num <= 1) return false;
if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root if (num2 % i === 0) { return false;
}
}
return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True

¿Por qué son tan útiles los números primos?

En Contact, el libro de ciencia ficción de Carl Sagan, los alienígenas envían una larga cadena de números primos como prueba de que su mensaje proviene de una fuerza vital inteligente. No estamos (todavía) comunicándonos con extraterrestres a través de números primos, pero los usamos de varias maneras aquí en el planeta Tierra.

Las cigarras emergen sincronizadas en ciclos de números primos exactos. Los ciclos irregulares significan que ningún depredador ha evolucionado para vivir de estos insectos. Además, el hecho de que todos emergan del suelo en el tiempo aumenta las posibilidades de supervivencia de un individuo.

Las pantallas utilizan números primos para definir las intensidades de color de los píxeles. También se utilizan en la fabricación de herramientas para deshacerse de las armonías. Dos engranajes que comparten un múltiplo engancharán los mismos dientes una y otra vez, lo que conduce a un patrón de desgaste desigual. Los engranajes que tienen un número primo de dientes en sus engranajes durarán más tiempo.

Sin embargo, los números primos son principalmente en la seguridad informática moderna. No es difícil encontrar números primos grandes, pero es muy difícil factorizar grandes números en números primos.

Es fácil averiguar que 27 es 3 x 3 x 3, pero es mucho más difícil encontrar que 2,244,354 es 2 x 3 x 7 x 53,437. Y 2.244.354 ni siquiera es un número tan grande. Encontrar los factores principales es técnicamente una cuestión de tiempo, pero debido a que tomará tanto tiempo, decimos que no se puede hacer.

Los algoritmos de cifrado modernos utilizan el hecho de que todavía no hay una computadora que pueda tomar un número súper grande y averiguar rápidamente qué números primos se utilizaron para hacerlo.

Es posible que esté comprando en línea o enviando un mensaje cifrado a través de una aplicación en su teléfono, pero en algún lugar, de alguna manera, los números primos le ayudan a mantener seguros sus secretos.

Aquí hay tres enlaces más a otros artículos de «Un algoritmo al día»:

Deja una respuesta

Tu dirección de correo electrónico no será publicada.