javascriptで素数関連。

以前上のような記事を書きましたが、今日はその発展編。javascriptで素数がらみのメソッドを作っていきたいと思います。

エラトステネスのふるい

ご存じ、素数を探すときの定番アルゴリズムですね。 手順は以下の通り。

1. 探索リストに2からxまでの数字を格納する。
2. 探索リストの先頭が素数となるのでこれを素数リストに格納・記録し、その倍数を探索リストからふるいおとす。
3. 探索リストの先頭がxの平方根に達するまで行う。
4. 探索リストに残った数字も実は素数。よってそれらを素数リストに移す。

素因数分解

これはエラトステネスのふるいがあれば簡単に求めることができます。

1. 2からxの平方根までの素数を求める。
2. 1でリストアップした素数で次々xを割っていく。
   • 同じ素数で複数回割れる可能性があることに注意する。
   • 割り切れるたびにxを更新することにも注意する。

素数判定

いろいろ方法はありますが、ここではいわゆる「試し割り」を利用しています。

1. 2からxの平方根までの整数を求める。
2. 1でリストアップした整数でxを割る。
   • ここではxを更新せずに次々割ることに注意する。
   • 途中で1回でも割り切れた場合、xは1とx以外に約数を持つので、素数ではない。

合成数判定

合成数（ごうせいすう、英: Composite number）は、自然数で、1とその数自身以外の約数を持つ数である。2つ以上の素数の積で表すことのできる自然数と定義してもよい。例えば15は1と15自身以外に3と5を約数に持つ（または[3×5]と素数の積で表される）ので合成数である。9や25など素数を2乗した数は1つしか素因数をもたないが、9=3×3 のように2つの素数の積で表せる合成数である。(wikipedia「合成数」より引用)

つまり素数ではない数字を合成数というわけです。ですから「素数判定」を応用すれば、「合成数判定」も簡単にできてしまいます。

1. 素数判定を行い、素数でなければ合成数。

まとめ

以上を実際にjavascriptで実装したものが以下となります。どれも簡単とはいえ、必要になるたびいちいち書くのは面倒な類でした。