素因数分解しよう

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

素因数分解とは、ある数を素数の掛け算で表すことです。2から順に割り切れるか試し、割り切れたらその数で割り続ける、という手順で求められます。暗号技術(RSA暗号など)の安全性の根拠にもなっている、数学とコンピュータサイエンスの両方にまたがる重要な考え方です。

サンプルコードでは、dという変数を2から順に増やしながら、nを割り切れる限り割り続けています。割り切れなくなったらdを1つ増やして次の数を試す、という手順をnが1になるまで繰り返すことで、すべての素因数をfactorsというリストに集めています。

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

素因数分解の結果を辞書にまとめて「何が何個あるか」を表示すると、より実用的な出力になります。コンピュータサイエンスの基礎理論とプログラミングのつながりを体感できる題材です。