質因數

說明

計算一個給定自然數的質因數。

質數只能被自己和 1 整除。

請注意，1 不是質數。

範例

60 的質因數是什麼？

• 我們的第一個除數是 2。 2 可以整除 60，剩下 30。
• 2 可以整除 30，剩下 15。
  • 2 無法整除 15。 所以我們換下一個除數 3 吧。
• 3 可以整除 15，剩下 5。
  • 3 無法整除 5。 下一個可能的因數是 4。
  • 4 無法整除 5。 下一個可能的因數是 5。
• 5 可以整除 5。
• 最後只剩下 1，所以我們就完成了。

在這段計算中，成功整除的除數就是 60 的質因數：2、2、3 和 5。

你可以自己驗證看看：

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

成功了！

---

出處

出自 Uncle Bob 的 The Prime Factors Kata。