列出将数字分解为 k 个因子的所有可能方法的算法？

Question

作为我通过 Euler 项目探索算法的一部分，我正在尝试编写一种方法，该方法将接受整数“n”、因子数“k”并对其进行因式分解。如果不可能，它会抛出错误。

例如，如果我输入 factorize(13257440,3)，该函数将返回包含 3 个元素的所有可能唯一集合的列表，其中 3 个元素的乘积等于 13257440。

我的第一个想法是生成一组 n 的素因子(“m”代表集合的大小)，然后将集合划分为 k 个分区。确定分区大小后，我会将其视为组合问题。

不过，我在为上述两个部分制定算法时遇到了麻烦，而且不知道从哪里开始。我是不是用一个简单的解决方案把一个简单的问题复杂化了？如果没有，有哪些推荐方法？谢谢!

Answer 1

1. 素数分解

   找到所有可以整除 n 无余数的素数。使用 Eratosthenes 筛法可大大加快该过程。

   你可以使用/修改我的(警告这个链接是项目欧拉剧透)

   • get primes up to n in C++

   现在您需要修改代码，使素数列表变为乘数列表。例如，如果 n=12 这将找到 { 2,3 } 并且您需要 { 2,2,3 } 所以如果找到除法素数一次又一次地检查它，直到它不再可分割为止，每次都减少 n。

   为每个找到的素数(已使用？)添加一个标志以加快下一步...

2. 组合部分

   我假设乘数可以是相同的，所以在开始时将 k 次 1 添加到素数列表并创建函数来创建数字的所有可能性直到某个 x 从找到未使用的素数。为未使用的素数添加计数器 m 因此在开始时 m 被设置为素数列表大小并且标志都被设置为未使用。

   现在您需要从列表中找到使用 1..m-k+1 数字的所有可能性。每次迭代都将选择的数字设置为已使用并减少 m，因此它类似于:

   for (o=1;o<=m-k+1;o++)
   

   在这里找到 o 未使用数字的所有组合，因此将其处理为 o 数字生成，基数 o 没有数字重复它是 o! 排列。

   你可以使用这个(警告这个链接是欧拉剧透):

   • permutations in C++

   不要忘记为每个使用的数字设置标志并在迭代完成后取消设置。重写此函数，使其迭代调用 findfirst()，findnext() 类似于我的排列类。

   现在您可以嵌套所有这些 k 次(使用来自排列链接的嵌套 for 或通过递归每次减少 k 和 n)