Prime Factorization
素因数分解とは、ある自然数をこれ以上分けられない素数の積に分解することです。 レゴを一つずつ外していくように、すべての合成数はちょうど一通りだけ素数の積で表せます。 同じ素因数を累乗でまとめ、各指数に1を足して掛ければ、約数の個数もすぐに分かります。 数をスライダーで変えると、因数分解の木と約数の格子がその数に合わせて描き直されます。
約数を漏れなく数えたり、あとで二つの数の公約数・公倍数を選んだりするには、その数をこれ以上割れない素数の積として先に書く方が速いです。その書き方が素因数分解で、同じ素因数は累乗にまとめます。掛け算の順を変えても素数と指数が同じなら結果は一つです。各指数に1を足して掛ければ約数の個数が出るので、まず数を素数まで分け切ることを扱います。
約数の格子には選んだ数の約数が円で置かれ、そのうち素因数はゴールドの円で区別されています。因数分解の木は数を下へ分け、葉がすべて素数になるまで描いてあります。同じ素因数が何度も出ると縦の割り算で累乗にまとめ、GCD・LCMの図には二つの数の共通素因数と指数の最小・最大が一緒に書いてあります。スライダーで数を変えると格子・木・一覧がその数に合わせて描き直されるだけで、枝が画面の上で伸びていくわけではありません。
1を素数と呼んだり、割る順番で素因数分解が変わると考えたりしやすいです。1の約数は一つだけなので素数でも合成数でもなく、いちばん小さい素数2だけが偶数でありながら素数です。同じ数をどの順で割っても素因数と指数は同じなので、結果は一通りです。割り算を一回で終わらせず、商が素数になるまで続けます。
素因数分解ではいちばん小さい素数から割り、商が素数になるまで同じことを繰り返します。同じ素数は累乗にまとめたあと、約数の個数を聞かれたら各指数に1を足して掛けます。大きい素数から割ると途中で詰まりやすいので、小さい素数から確かめます。この順を守れば、格子で見たゴールドの円と同じ一覧になります。
素因数と指数で書いておけば、次の章ではGCDを共通素因数の指数の最小、LCMをすべての素因数の指数の最大としてすぐ選べます。GCD×LCM=a×bの関係も同じ書き方の上にあります。最小と最大を混ぜると両方が入れ替わるので、二つの数の素因数の一覧を並べて指数を比べます。