Défis JavaScript : nombres premiers et nombres premiers de Sophie Germain

Nombres premiers

Que sont les Nombres Premiers ?

Un nombre premier est un nombre entier supérieur à 1 qui ne peut être exactement divisé par un nombre entier autre que lui-même et 1 (par exemple 2, 3, 5, 7, 11).

Le nombre 5 est un nombre premier car ses seuls diviseurs sont 1 et 5.

Le nombre 4 n'est pas un nombre premier car ses diviseurs sont 1, 2 et 4.

Créons une fonction qui renverra true si string est un nombre premier et renverra false si un nombre n'est pas un nombre premier .

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

Créons une fonction

 function isPrime(num) { }

Un nombre premier est un nombre supérieur à 1. Ainsi, un nombre inférieur à 1 n'est pas un nombre premier.

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

 isPrime(-5); // false

L' opérateur modulo est utilisé pour obtenir le reste après la division. Nous allons vérifier si le nombre peut être divisé en d'autres facteurs (sauf 1 et lui-même) sans laisser de reste.

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

N'oubliez pas que 2 est un nombre premier.

 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

Que faire si nous avons un grand nombre?

 isPrime(56669900033);

Notre fonction fonctionnera plus lentement. Nous pouvons raccourcir le processus en utilisant la racine carrée. Par exemple,

nombre 121. La racine carrée de 121 est 11 . Cela signifie que 121 n'est pas un nombre premier , car un nombre premier ne peut être divisé en parts égales que par lui-même et 1. Ainsi, au lieu d'itérer de 2 à 121 , nous pouvons simplement itérer jusqu'à 11 inclus, la racine carrée de 121 .

Math.sqrt() trouve la racine carrée d'un nombre.

 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 Premiers

Si p et 2p+1 sont premiers, alors p est un premier de Sophie Germain . Par exemple, 2, 3, 5, 11, 23, 29, 41, 53, 83, 89…

5 est un nombre premier et 5*2+1=11

11 est aussi un nombre premier . Ainsi, 5 et 11 sont des nombres premiers de Sophie Germain.

Créons une fonction qui renverra un tableau de nombres premiers de Sophie Germain de 2 à n.

Nous allons utiliser notre fonction isPrime() de l'exemple précédent pour vérifier si le nombre est premier.

 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]

J'espère que vous avez trouvé cela utile !