JavaScript 挑战：素数和 Sophie Germain 素数

质数

什么是素数？

素数是一个大于 1 的整数，它不能被除了它本身和 1 以外的任何整数整除（例如 2、3、5、7、11）。

数字 5 是质数，因为它的因数只有 1 和 5。

数字 4不是质数，因为它的因子是 1、2 和 4。

让我们创建一个函数，如果字符串是素数则返回true ，如果数字不是素数则返回false 。

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

让我们创建一个函数

function isPrime(num) { }

质数是大于 1 的数。因此，小于 1 的数不是质数。

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

 isPrime(-5); // false

模运算符用于获取除法后的余数。我们要检查num是否可以在不留余数的情况下除以其他因子（除了 1 和它本身）。

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

请记住，2 是质数。

 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

如果我们有一个巨大的数字怎么办？

 isPrime(56669900033);

我们的功能会运行得更慢。我们可以使用平方根来缩短这个过程。例如，

数字121。121的平方根是11 。这意味着121不是质数，因为质数只能被其自身和 1 整除。因此，我们可以迭代到并包括11 ，即 121 的平方根，而不是从2迭代到121 。

Math.sqrt()求一个数的平方根。

 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

苏菲热尔曼素数

如果 p 和 2p+1 都是素数，则 p 是索菲热尔曼素数。例如，2、3、5、11、23、29、41、53、83、89……

5是素数， 5*2+1=11

11也是质数。所以， 5和11都是Sophie Germain 素数。

让我们创建一个函数，它将返回从2到n的Sophie Germain 素数数组。

我们将使用前面示例中的isPrime()函数来检查数字是否为素数。

 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]

我希望你觉得这有帮助！