素因数分解するだけ

きっかけ

「秒単位の時間かからないでしょ」って意見出回ってたし、僕もそう思った。

ただしどうやらこれは例えだった模様。
その後

まあそうだわな。
C使ってるっぽいからコンパイルに秒単位の時間はかかりそうかもね。

JavaScriptでサクっと書いてみた。

Part.1 vueで書く

僕が仕事でvue.js使ってるのもあるし、DOMの取得とか書くのめんどくさがるにんげんなので、vueでてけとーに書いちゃうクセがあるんだよね。

で、できたのが

<script src="https://unpkg.com/vue@3/dist/vue.global.js"></script>
<div id="app">
  <input type="number" style="font-size: large;" name="input" min="1" v-model="input">
  <ul>
    <li v-if="!list.length">nothing</li>
    <li v-for="x in list">{{x[0]}} ^ {{x[1]}}</li>
  </ul>
</div>
<script>
  const app = Vue.createApp({
    data() { 
      return { input: 10, }
    },
    methods: {
      fact: function (src, div, count = 0) { // src を div で割るときに、
        // 割った余りがあれば割り切れないので結果を返す。 なければ再帰処理
        return src % div ? (count && [src, [div, count]]) // 割れなければ 0, 割れたら [割った結果, [div, 割った回数]] が返る
                         : this.fact(src / div, div, count+1);
      },
      test: function (x, div) { // 
        let tmp = this.fact(x.src, div);
        if (!tmp) return;
        x.src = tmp[0];
        x.res.push(tmp[1]);
      },
    },
    computed: { // computed なので値更新に伴い自動更新される
      list: function () {
        let x = { src: this.input, res: [] }; // src:因数分解途中の値, res: [...[割れた数, 割れた数で割った回数]]
        if (x.src < 1) return [];
        this.test(x, 2); // 素数判定と同じような感覚で
        for (let i = 3; i <= x.src; i += 2) { // ほんとは sqrt にして良い。
          this.test(x, i);
        }
        return x.src === 1 ? x.res : x.res.concat([[x.src, 1]]);
        // push の返り値は要素追加後の length が返るが、 concat なら配列を繋げた結果が返る。
        // もともとの Array は変更しない。メモリ消費量はﾁｮｯﾄ不利だけど記述が短くできる。
      }
    }
  });
  app.mount('body>div');
</script>

特に解説するようなことは無いです。
因数分解処理を再帰処理で書いたのが美しいなって自画自賛があるくらいです。

Part.2 ヴァニラな JS で書く

ライブラリ使わないで書いただけ

<input name="input" type="number" style="font-size: large;" min="1">
<ul></ul>
<script>
  let x;
  let $ = t => document.querySelector(t); // 一番良く使われる jQuery の使われ方の今回用事のある範囲での実装。
  let inpel = $("input");
  let uel = $("ul");
  inpel.addEventListener("input", e => { assign(list()); });
  let assign = (list) => {
    l = list.length ? list.map(v => `${v[0]} ^ ${v[1]}`) : ["nothing"];
    uel.innerHTML = "";
    l.forEach(t => uel.appendChild(document.createElement("li")).innerText = t);
    // appendChild は通常、 append された要素(≒引数) を返すので、メソッドチェーンに組み込める
  };
  let fact = (src, div, count = 0) => src % div ? (count && [src, [div, count]]) : fact(src / div, div, ++count);
  let test = div => {
    let tmp = fact(x.src, div);
    if (!tmp) return;
    x.src = tmp[0];
    x.res.push(tmp[1]);
  };
  let list = () => {
    x = { src: inpel.value, res: [] };
    if (x.src < 1) return [];
    test(2);
    for (let i = 3; i <= x.src; i += 2) {
      test(i);
    }
    return x.src === 1 ? x.res : x.res.concat([[x.src, 1]]);
  };
</script>

Part.3 ヴァニラな JS で書いたのを Minify する

いろいろやって短くしました。

<input name="input" type="number" style="font-size: large;" min="1">
<ul></ul>
<script>
  A=t=>U.appendChild(document.createElement("li")).innerText=t;
  (I=($=t=>document.querySelector(t))("input")).addEventListener("input",e=>{
    (U=$("ul")).innerHTML="";
    I.value&&(l=(x,i=2)=>i>x?(x-1||!U.innerHTML?A(`${x}^1`):0):((b=(s,c=0)=>s%i?c&&(x=s)&&A(`${i}^${c}`):b(s/i,c+1))(x),l(x,i+1+i%2)))(I.value);
  });
</script>

配列にしてforEach をやめる

整理のためには配列にデータ載せてからあとで描画処理する流れは、脳内の整理のためにも都合が良い。

が、結果だけあってれば良い文脈なら出力順が正しくなってれば別に見敵必殺してもよいのである
割り算の結果が出次第出力を追加するための関数を短い名前で作っておけばあちこちで呼んでも短くできる。
明らかに最初に呼び出される呼び出し箇所があれば、そこに追加すれば良いが、下記関数はそれができないので事前宣言している。

  A=t=>U.appendChild(document.createElement("li")).innerText=t;

Uは未定義のようで、結局イベント発生時に呼び出されるのでそのスコープで定義されていれば良い。ここではul要素

for 文を再帰処理に

  let list = () => {
    x = { src: inpel.value, res: [] };
    if (x.src < 1) return [];
    test(2);
    for (let i = 3; i <= x.src; i += 2) {
      test(i);
    }
    return x.src === 1 ? x.res : x.res.concat([[x.src, 1]]);
  };

ループ変数を引数に持つ関数にして、引数を次のループの値で更新して呼び出す再帰関数にする

だいたい以下のように変換する

f = (パラメタ)          => { for(i=初期値;継続条件;i = 次(i)){ ループ処理(パラメタ); } return 返り値; }
g = (パラメタ, i=初期値) => { if(!継続条件){ return 返り値; } ループ処理(パラメタ); return g(パラメタ, 次(i)) }

Mini = (パラメタ, i=初期値) => !継続条件? 返り値: (ループ処理(パラメタ),Mini(パラメタ, 次(i)))

ちなみにMinifyerに食わせれば短くしてくれるけど、再帰処理にするとかまではできない（そらそうだ）