分解质因数

实践练习C++17

素数是大于 1、且只有 1 和自身两个正因数的整数。分解质因数时,重复出现的因子也需要保留。

任务说明

计算给定自然数的质因数分解。

质数只能被 1 和自身整除。

注意,1 不是质数。

示例

60 有哪些质因数?

  • 从除数 2 开始,60 除以 2 得到 30。
  • 30 再除以 2 得到 15;15 不能被 2 整除,换下一个除数 3。
  • 15 除以 3 得到 5;5 不能被 3 整除,再尝试 4;4 也不行,继续到 5。
  • 5 除以 5 得到 1。
  • 只剩 1,分解结束。

成功使用的除数就是 60 的质因数列表:2、2、3、5。

可以自行验证:

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

验证成功!