素因数分解しよう

このレッスンでは、ある数を素数の掛け算で表す素因数分解のアルゴリズムを学び、数学とプログラミングのつながりを体験することを目標にします。「JavaScript 素因数分解」で検索している方向けの内容です。

素因数分解とは、ある数を素数の掛け算で表すことです。2から順に割り切れるか試し、割り切れたらその数で割り続ける、という手順で求められます。素因数分解の結果を使うと、最大公約数や最小公倍数を求める別の方法としても応用できます。

サンプルコードでは、dという変数を2から順に増やしながら、nを割り切れる限り割り続けています。割り切れなくなったらdを1つ増やして次の数を試す、という手順をnが1になるまで繰り返すことで、すべての素因数をfactorsという配列に集めています。60と97(これは素数です)を試して結果の違いを確認してみましょう。

初心者がよくつまずくのが、内側と外側、2つのループの役割の違いです。内側のループは「同じ数で何回割り切れるか」を、外側のループ(while)は「次に試す数へ進める」役割を持っています。この2段階の構造を理解すると、アルゴリズム全体の流れが見えてきます。

暗号技術(RSA暗号など)の安全性の根拠にもなっている、数学とコンピュータサイエンスの両方にまたがる重要な考え方です。コンピュータサイエンスの基礎理論とプログラミングのつながりを体感できる題材です。