JavaScript の課題: 素数とソフィー ジェルマン素数

素数

素数とは？

素数とは、それ自体と 1 以外の整数で正確に割り切れない 1 より大きい整数です (例: 2、3、5、7、11)。

5 は約数が 1 と 5 しかないので素数です。

4 は約数が 1、2、4 であるため、素数ではありません。

string が素数の場合に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です。これは、素数はそれ自体と 1 でしか割り切れないため、 121は素数ではないことを意味します。したがって、 2 から 121まで反復する代わりに、 121の平方根である11まで反復することができます。

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 はSophie Germain 素数です。たとえば、2、3、5、11、23、29、41、53、83、89…

5は素数で、 5*2+1=11

11も素数です。つまり、 5と11は両方ともソフィー・ジェルマンの素数です。

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]

これがお役に立てば幸いです。