Algorithms - JavaScript - 基礎概念 - 数学的な基礎(帰納法、素因数分解)

The Art of Computer Programming
Volume 1
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• Node.js, Safari(JavaScript エンジン)
• Learning JavaScript [邦訳](参考書籍)

The Art of Computer Programming　Volume 1 Fundamental Algorithms Third Edition 日本語版(Donald E. Knuth (著)、青木 孝 (著)、筧 一彦 (著)、鈴木 健一 (著)、長尾 高弘 (著)、有澤 誠 (その他)、和田 英一 (その他)、ドワンゴ)の第1章(基礎概念)、1.2(数学的な基礎)、演習問題5を取り組んでみる。

5. 
   $\begin{array}{l}2は素数\\ n+1が素数の場合は成り立つ。\\ n+1が素数ではない場合。\\ n+1=a·b\\ a\le n,b\le n\\ 帰納法の仮定より、a、bは素数の積として表現できる。\\ ゆえに、\\ n+1=a·b\\ は素数の積として表現できる。\end{array}$

コード(Emacs)

HTML5

n = <input id="n0" type="number" min="2" step="1" value="100">
<br>
<button id="run0">run</button>
<button id="clear0">clear</button>
<pre id="output0"></pre>

<script src="sample5.js"></script>

JavaScript

let input0 = document.querySelector('#n0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    pre0 = document.querySelector('#output0'),
    p = (x) => pre0.textContent += x + '\n';

let primes = [undefined, undefined, true];
let isPrime = (n) => {
    if (primes[n] === undefined) {
        for (let i = 2; i <= n / 2; i += 1) {
            if (n % i === 0) {
                primes[n] = false;
                return false;
            }
        }
    }
    primes[n] = true;
    return true;
};
let isInt = (x) => Math.floor(x) === x;

let f = (n) => {
    for (let i = 2; i <= n; i += 1) {
        isPrime(i);
    }
    let result = '';
    for (let i = 2; i <= n; i += 1) {
        if (isPrime(i)) {
            console.log(i);
            let j = 0;
            for (; isInt(n / i);) {
                n /= i;
                j += 1;
                if (n === 1)  {
                    if (j === 1) {
                        result += `${i}`;
                    } else if (j > 1) {
                        result += `${i}^${j}`;
                    }
                    return result;
                }
            }
            if (j === 1) {
                result += `${i} * `;
            } else if (j > 1) {
                result += `${i}^${j} * `;
            }
        }
    }
};

let output = () => {
    let n = parseInt(input0.value, 10);

    for (let i = 2; i <= n; i += 1) {
        p(`${i} = ${f(i)}`);
    }
};
    

btn0.onclick = output;
btn1.onclick = () => {
    pre0.textContent = '';
};

output();

n =