Lesson17: アルゴリズム（素因数分解）

このサイトは移転しました。1秒後に自動でジャンプします。
移動しない場合は、ここをクリックしてください。

---

車の仕組みが分からなくても車の運転ができるように、コンピュータの仕組みがわからなくても、豊富なアプリケーションを使いこなして、たいていのやりたいことはできると思います。

それでもなお、息子にコンピュータの仕組みやプログラミングについて学んでほしいと考えているのは、プログラミングを通じて、考える力を身につけてほしいと考えるからです。

例えば、ある数値の素因数分解を行うとき、素数の順に割れるかどうかを見て素因数を求めていきます。このように、問題を解く手順のことをアルゴリズムと呼び、プログラミングとは、そのアルゴリズムを記述することにほかなりません。

プログラムを書いてしまえば、面倒くさい計算はコンピュータが実行してくれます。
小さい頃は四則演算などを一生懸命練習して計算力を身につけることはとても重要なのですが、それなりに計算ができるようになったら、どのようにすれば解けるのかというアルゴリズムを考えてカタチにする力をつけていってほしいと思います。

今回は、素因数分解を行うJavaScriptを書いてみました。
まだ素因数分解を習っていない？　そんなルールに縛られることなく、知っていることを教えていきたいと思います。
今はまだよく理解できなかったとしても、いつかそうした断片的な知識がつながる瞬間がくると確信しています。

https://github.com/toshio/js4son/blob/master/chapter02/lesson17.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Lesson17 Prime factorization</title>
  <body>
    <input id="number" type="number" min="2" max="10000" placeholder="Number" onchange="answer();"/>
    <input id="result" type="text"   maxlength="40" placeholder="result" readonly="readonly" />
    <script>
    function answer() {
        var number  = parseInt(document.getElementById("number").value);
        var value   = "";
        if (number) {
            value = factorize(number).join(" × ");
        }
        document.getElementById("result").value = value;
    }

    function factorize(value) {
        var factors = [];
        var divisor = 2;
        while (value >= 2) {
            if (value % divisor == 0) {
                value /= divisor;
                factors.push(divisor);
            } else {
                divisor++;
            }
        }
        return factors;
    }
    </script>
  </body>
</html>

素因数分解は、素数で割っていくことが基本ですので、そもそも2以外の偶数で割る必要がないなどを考慮すれば、もっと計算量の少ないアルゴリズムがかけると思います。