素因数

説明

与えられた自然数の素因数を計算します。

素数とは、1とその数自身でしか割り切れない数です。

なお、1は素数ではありません。

例

60の素因数は何でしょうか？

• 最初の約数は2です。 60は2で割り切れて、30が残ります。
• 30は2で割り切れて、15が残ります。
  • 15は2では割り切れません。 そこで、次の約数である3に進みましょう。
• 15は3で割り切れて、5が残ります。
  • 5は3では割り切れません。 次に考えられる因数は4です。
  • 5は4でも割り切れません。 次に考えられる因数は5です。
• 5は5で割り切れます。
• 残ったのは1だけなので、これで終わりです。

この計算で割り切れた約数が、60の素因数のリストになります。2、2、3、5です。

自分で確認することもできます。

2 * 2 * 3 * 5
= 4 * 15
= 60

成功です！

---

出典

Uncle BobによるThe Prime Factors Kata