list - 生成一个数的质因数

Question

我正在尝试编写一个函数，该函数给出Int大于一的非递减列表，该列表由该数字的主要因素（重复）组成

示例：n = 12，输出应该是[2,2,3]

我不知道从哪里开始。

Answer 1

当然，对于您想要做的事情，有众所周知的算法，所以简单的谷歌搜索真的可以解决这个问题。

但是，我想向您展示一个简单的思考过程，它可能对未来有所帮助。

由于因子必须按升序出现，您可以：

1. 从最低的素数 (2) 开始。
2. 检查数字是否可以除以它。如果可以，请执行并返回1。
3. 如果不是，则将 2 替换为下一个素数并返回2。

现在，很明显，您将检查的最大质数是您开始使用的数字。但是，基本乘法公理指出，如果一个数可以除以a：

n / a = b

那么也可以除以b！您可以使用该事实来进一步缩小检查范围，但我会留给您计算（或谷歌）上限。

实际的实现当然是你功课的一部分，因此在这里提供代码不是一个明智的主意。但是，我认为诸如此类的东西next_prime对您来说并不难。