「素数を調べる(ループ処理2)」では、'for'や'while'アクションを使って素数を求めるスクリプトを2つご紹介しました。素数というものの性質を理解すると、さらに処理の速いスクリプトを構成することができます。

まず、素数になれる(1より大きい)最初の整数は2です。当然これより小さい素数はありえませんから、素数の掛合わせで表せるはずもありません。つまり、2が最初の素数です。

つぎに小さい整数は、3です。これより小さい素数は2ですが、3を割ると余りが出てしまいます。ですから、3も素数です。4は、これより小さい2つの素数の内、2で割切れます。つまり、2×2で表せますので、素数ではありません。

この考え方で組み立てたスクリプトが、以下のサンプルです。関数をつぎのように実行すると、100までのすべての素数が出力ウィンドウに表示されます。

// 関数のテスト例
trace (xGetPrimeNumbers(100));
// 出力ウィンドウの表示
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

// [素数を配列で返す関数]
// 引数nMax: 素数を調べる整数の最大値
function xGetPrimeNumbers (nMax) {
   var lResult = new Array();
   if (nMax<2 || typeof nMax != "number") {
     return lResult;
   }
   // [1]最初の素数2を配列に格納
   lResult.push(2);
   // [2]3から指定された最大値の整数までを調べる
   // ただし奇数のみ
   for (var i = 3; i<=nMax; i += 2) {
     var bPrime = true;
     var n = 0;
     // [3]配列の'length'プロパティの値を変数に設定
     var nLength = lResult.length;
     // [4]それまでのすべての素数で割ってみる
     while (n<nLength) {
       if (!(i%lResult[n])) {
         bPrime = false;
         break;
       }
       n++;
     }
     if (bPrime) {
       lResult.push(i);
     }
   }
   return lResult;
}

スクリプトについて、コメントでつけたナンバーにしたがって、簡単に解説します。'for'や'while'アクションを使ったループ処理のスクリプティングについては、「1から連番の配列をつくる(ループ処理)」および前掲「素数を調べる(ループ処理2)」を併せてご覧ください。また、使用しているメソッドやアクション、演算子などについて、詳しくは「ActionScript辞書」をご参照ください。

[1] 結果を納める配列に、まず最小の素数2を加えておきます。以下の素数を調べる処理では、配列に格納された素数で割切れるかどうかを判定していくからです。

[2] 2は素数としてすでに結果を納める配列に入れましたので、調べるのは3から引数で指定された最大の整数までです。ここでひとつのポイントは、変数の更新で、変数iを2ずつ増加させていることです。これは、素数2で割切れる整数つまり偶数は素数でないことが明らかなので、奇数だけ確認すれば十分だからです。

[3] 素数を格納した配列の要素数'length'プロパティの値を、ローカル変数に設定しています。この値は、つぎの'while'アクションで、終了条件を定義する値として使います。

だとすれば、[4]の'while'アクションの終了条件を(n<lResult.length)としておけば、このステートメントは不要に見えます。それは、そのとおりです。ただ、ループ処理で繰り返し条件を評価する場合には、配列のプロパティにアクセスするより、変数に設定した値を取り出す方が速いのです。ここは、スピードを重視するか、シンプルで見やすいスクリプトを採るかによって、記述を変えて結構です。

[4] ここで、冒頭で述べた素数の判定方法を使っています。つまり、[2]の'for'アクションで小さい順に調べている現在の整数を、すでに配列に格納したそれより小さい素数すべてで割ってみます。その整数より小さい配列のすべての素数で割り切ることができなければ、その整数も素数です。

その判定を、つぎの'if'アクションで行っています。'if'アクションの条件は、論理式ではありません。この場合、式の値が0つまり割切れたときに'true'となります(条件が論理式でない場合の評価については、前掲「素数を調べる(ループ処理2)」参照)。 割切れたときは、素数ではありません。'if'アクションの中のステートメントが実行され、素数であることを示す変数bPrimeに'false'が設定されます。そして、素数でないことが判明した以上、この整数についてもはや調べる必要がありませんので、'break'アクションにより'while'ループの処理を抜けます。

'if'条件が'true'と評価されずに'while'アクションを終了した場合、変数bPrimeの値は'for'アクションの最初に設定された初期値'true'のままです。したがって、'while'アクションの処理の後に、この変数が'true'か'false'かによって、素数かそうでない(合成数)かが判定できる訳です。最後の'if'アクションは、この変数が'true'の場合に、配列にその整数つまり素数を追加します。

上述のスクリプトの処理も、考え方としては、これと同じです。ただ、手順として、まず素数の倍数をすべて除くというのではなく、調べる対象の整数を小さい順にひとつひとつすべての素数で割ってみるという点に違いがあるに過ぎません。

今回のスクリプトのように素数の配列を使わずに、2以上のすべての整数で割った結果を調べる前掲「素数を調べる(ループ処理2)」のサンプルスクリプトのような例でも、素数の性質を知っていると効率化できます。たとえば、100以下のある整数が素数かどうか調べるのに、2からいくつまでの整数で割ってみれば判定できるでしょうか。前掲ノートでご紹介したサンプルの場合には、整数値の半分つまり50としました。けれど、実は10まで調べれば十分なのです。

それは、なぜでしょう。ここで、筆者が嘘をいっているとします。つまり、その100以下の整数が2から10までで割切れなくても、もっと大きい整数で割切れると仮定します。すると、その10より大きい整数で割った商も、当然10より大きいことになります。10以下の整数で割切れないことは、調べ済みなのですから。そうすると、その整数は、10より大きい2つの整数を掛合わせた値に等しいということになってしまいます。つまり、100より大きい整数だということです。この矛盾は、10より大きい整数で割切れたとする仮定から生じたものです。

一般に、2から順に割って調べる整数の値は、割られる整数の平方根('Math.sqrt')の値までで足りるのです。