作为我通过 Euler 项目探索算法的一部分,我正在尝试编写一种方法,该方法将接受整数“n”、因子数“k”并对其进行因式分解。如果不可能,它会抛出错误。
例如,如果我输入 factorize(13257440,3),该函数将返回包含 3 个元素的所有可能唯一集合的列表,其中 3 个元素的乘积等于 13257440。
我的第一个想法是生成一组 n 的素因子(“m”代表集合的大小),然后将集合划分为 k 个分区。确定分区大小后,我会将其视为组合问题。
不过,我在为上述两个部分制定算法时遇到了麻烦,而且不知道从哪里开始。我是不是用一个简单的解决方案把一个简单的问题复杂化了?如果没有,有哪些推荐方法?谢谢!
最佳答案
素数分解
找到所有可以整除
n
无余数的素数。使用 Eratosthenes 筛法可大大加快该过程。你可以使用/修改我的(警告这个链接是项目欧拉剧透)
现在您需要修改代码,使素数列表变为乘数列表。例如,如果
n=12
这将找到{ 2,3 }
并且您需要{ 2,2,3 }
所以如果找到除法素数一次又一次地检查它,直到它不再可分割为止,每次都减少n
。为每个找到的素数(已使用?)添加一个标志以加快下一步...
组合部分
我假设乘数可以是相同的,所以在开始时将
k
次1
添加到素数列表并创建函数来创建数字的所有可能性直到某个x
从找到未使用的素数。为未使用的素数添加计数器m
因此在开始时m
被设置为素数列表大小并且标志都被设置为未使用。现在您需要从列表中找到使用
1..m-k+1
数字的所有可能性。每次迭代都将选择的数字设置为已使用并减少m
,因此它类似于:for (o=1;o<=m-k+1;o++)
在这里找到
o
未使用数字的所有组合,因此将其处理为o
数字生成,基数o
没有数字重复它是o!
排列。你可以使用这个(警告这个链接是欧拉剧透):
不要忘记为每个使用的数字设置标志并在迭代完成后取消设置。重写此函数,使其迭代调用
findfirst()
,findnext()
类似于我的排列类。现在您可以嵌套所有这些
k
次(使用来自排列链接的嵌套for
或通过递归每次减少k
和n
)
关于列出将数字分解为 k 个因子的所有可能方法的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30543342/