Desafios de JavaScript: números primos e primos de Sophie Germain

Números primos

O que são números primos ?

Um número primo é um número inteiro maior que 1 que não pode ser exatamente dividido por nenhum número inteiro que não seja ele mesmo e 1 (por exemplo, 2, 3, 5, 7, 11).

O número 5 é um número primo porque seus únicos divisores são 1 e 5.

O número 4 não é um número primo porque seus fatores são 1, 2 e 4.

Vamos criar uma função que retornará true se string for um número primo e retornará false se um número não for primo .

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

Vamos criar uma função

 function isPrime(num) { }

Um número primo é um número maior que 1. Portanto, um número menor que 1 não é um número primo.

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

 isPrime(-5); // false

O operador módulo é usado para obter o resto após a divisão. Vamos verificar se o num pode ser dividido em outros fatores (exceto 1 e ele mesmo) sem deixar resto.

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

Lembre -se que 2 é um 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

E se tivermos um número enorme?

 isPrime(56669900033);

Nossa função será executada mais lentamente. Podemos encurtar o processo usando a raiz quadrada. Por exemplo,

número 121. A raiz quadrada de 121 é 11 . Isso significa que 121 não é um número primo , porque um número primo só pode ser dividido igualmente por ele mesmo e por 1. Portanto, em vez de iterar de 2 a 121 , podemos apenas iterar até 11 inclusive, a raiz quadrada de 121 .

Math.sqrt() encontra a raiz quadrada de um 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

Sophie Germain Primes

Se p e 2p+1 são primos, então p é um primo de Sophie Germain . Por exemplo, 2, 3, 5, 11, 23, 29, 41, 53, 83, 89…

5 é um número primo e 5*2+1=11

11 também é um número primo . Então, tanto 5 quanto 11 são números primos de Sophie Germain.

Vamos criar uma função que retornará um array de números primos de Sophie Germain de 2 até n.

Usaremos nossa função isPrime() do exemplo anterior para verificar se o número é 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]

Eu espero que tenha achado isto útil!