Desafíos de JavaScript: números primos y números primos de Sophie Germain

Números primos

¿Qué son los números primos ?

Un número primo es un número entero mayor que 1 que no se puede dividir exactamente por ningún número entero que no sea él mismo y 1 (por ejemplo, 2, 3, 5, 7, 11).

El número 5 es un número primo porque sus únicos factores son 1 y 5.

El número 4 no es un número primo porque sus factores son 1, 2 y 4.

Vamos a crear una función que devolverá verdadero si la cadena es un número primo y devolverá falso si un número no es primo .

 isPrime(3); // true isPrime(9); // false

Vamos a crear una función

 function isPrime(num) { }

Un número primo es un número mayor que 1. Entonces, un número menor que 1 no es un número primo.

 function isPrime(num) { if (num <= 1) return false; }

 isPrime(-5); // false

El operador módulo se usa para obtener el resto después de la división. Vamos a comprobar si el num se puede dividir en otros factores (excepto en 1 y en sí mismo) sin dejar resto.

 function isPrime(num) { if (num <= 1) return false; for (let i=2; i<num; i++) { if (num%i !== 0) return false; } return true; }

Recuerda que el 2 es un número primo.

 function isPrime(num) { if (num <= 1) return false; if (num === 2) return true; for (let i=2; i<num; i++) { if (num%i === 0) return false; } return true; }

 isPrime(5); //true isPrime(9); //false

¿Qué pasa si tenemos un gran número?

 isPrime(56669900033);

Nuestra función se ejecutará más lentamente. Podemos acortar el proceso usando la raíz cuadrada. Por ejemplo,

número 121. La raíz cuadrada de 121 es 11 . Esto significa que 121 no es un número primo , porque un número primo solo se puede dividir en partes iguales entre sí mismo y 1. Entonces, en lugar de iterar de 2 a 121 , podemos iterar hasta 11 inclusive, la raíz cuadrada de 121 .

Math.sqrt() encuentra la raíz cuadrada de un número.

 function isPrime(num) { if (num <= 1) return false; if (num === 2) return true; let numSqrt = Math.sqrt(num); for (let i=2; i<=numSqrt; i++) { if (num%i === 0) return false; } return true; }

 isPrime(5); //true isPrime(121); //false

Primos de Sophie Germain

Si tanto p como 2p+1 son primos, entonces p es un primo de Sophie Germain . Por ejemplo, 2, 3, 5, 11, 23, 29, 41, 53, 83, 89…

5 es un número primo y 5*2+1=11

11 también es un número primo . Entonces, tanto el 5 como el 11 son números primos de Sophie Germain.

Vamos a crear una función que devuelva una matriz de números primos de Sophie Germain desde 2 hasta n.

Usaremos nuestra función isPrime() del ejemplo anterior para verificar si el número es primo.

 function getGermainPrimes(n) { let result = []; // an array of Sophie Germain prime numbers (our result) for (let i = 0; i <= n; i++) { if (isPrime(i) && isPrime(i*2 + 1)) { //if both i and 2i+1 are prime result.push(i); } } return result; }

 getGermainPrimes(100); // [2, 3, 5, 11, 23, 29, 41, 53, 83, 89]

¡Espero que hayas encontrado esto util!