素因数分解しよう

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

素因数分解とは、ある数を素数の掛け算で表すことです。2から順に割り切れるか試し、割り切れたらその数で割り続ける、という手順で求められます。

サンプルコードでは、dという変数を2から順に増やしながら、nを割り切れる限り割り続けています。factors << dという書き方で配列に要素を追加している点も、Rubyらしい簡潔な記法です。

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

暗号技術(RSA暗号など)の安全性の根拠にもなっている、数学とコンピュータサイエンスの両方にまたがる考え方です。1という数はどんな数でも割り切れてしまうため、素因数分解の対象からは除外して考える必要があります。