素数かどうかを判定しよう

このレッスンでは、ある数が素数かどうかを判定するアルゴリズムを学び、効率的な判定方法を理解することを目標にします。「JavaScript 素数判定」「素数 アルゴリズム」で検索している方向けの内容です。

ある数が素数(1とその数自身でしか割り切れない数)かどうかは、2から「その数の平方根」までの数で割り切れるかを調べればわかります。すべて割り切れなければ素数です。1つずつすべての数で割ってみるより、平方根までで判定を打ち切ることで計算を大幅に減らせるのがポイントです。

サンプルコードでは、i * i <= nという条件を使うことで、実質的に「平方根まで」の範囲だけをループしています。Math.sqrt()を使わずにこの書き方をすることで、平方根の計算コスト自体も省略できる、少し工夫されたアルゴリズムになっています。17と18という2つの数で結果を比べてみましょう。

初心者がよくつまずくのが、なぜ平方根までしか調べなくてよいのかという理屈です。ある数を割り切る2つの数のペアは、必ず一方が平方根以下、もう一方が平方根以上になるため、平方根以下の範囲だけ調べれば十分だという性質を利用しています。効率のよい判定方法を考えることは、アルゴリズムの基礎を学ぶ良い練習になります。

暗号技術の基礎にも使われる重要な数学的性質で、効率よく判定するアルゴリズムを考えることは、コンピュータサイエンスの基本の1つです。インターネットの通信を暗号化するRSA暗号などでも、大きな素数を扱う計算が根幹の技術として使われています。