分解超过100位数字的整数

Question

X和Y是大于100位数字的整数。找到在范围[X,Y[内的整数P，它保证具有“最佳”素数分解（即具有最多唯一质因数的分解）。

我所做的只是检查质数并分解范围内的每个数字，找到符合规则的数字。还有其他方法吗？

小整数的示例

编辑：

在上面的例子中，123456被分解为
2^6 * 3^1 * 643^1，即2 * 2 * 2 * 2 * 2 * 2 * 3 * 643，但只有3个唯一因数。

而答案123690被分解为6个唯一因数
2^1 * 3^1 * 5^1 * 7^1 * 19^1 * 31^1。

- Jonas

---

在网上搜索“c++大数库”，因为有很多选择。 - Thomas Matthews

X和Y大于100位数字的目的可能是为了禁止您计算每个可能数的分解。在我看来，这里有趣的事情是找到一种不需要进行这种计算的算法。 - Arnaud Denoyelle

我开始写一个答案，但是找不到一个精确的算法。我的想法是将它倒置。类似于尝试 P = 2*2*2*....*2。如果它在 X 和 Y 之间，你就赢了。否则，尝试 P = 2*2*2*.... *3等等。递归地尝试每个可能的乘法，使用最小的数字。 - Arnaud Denoyelle

这个问题似乎不适合讨论，因为它涉及到数论。 - Brett Hale

此问题似乎与编程无关，属于数论范畴。 - user149341

Answer 1

关于列举质数的问题，答案总是找到一种使用筛法解决问题的方法；在您的情况下，您正在寻找具有大量因子的“反质数”，但原则仍然适用。

这个问题的关键是，对于大多数数字，大多数因子都很小。因此，我的建议是为范围X到Y设置一个筛子，其中包含所有初始化为零的整数。然后考虑所有小于某个限制的质数，尽可能大，但显然比X小得多。对于每个质数，将是该质数的倍数的筛子的每个元素加1。在使用所有质数筛选后，具有最大计数的筛选位置对应于在X和Y之间具有最多不同质因数的数字。

让我们考虑一个例子：取范围100到125，并使用2、3、5和7这些质数进行筛选。你会得到像这样的结果：

100 2 5
101 (101)
102 2 3 (17)
103 (103)
104 2 (13)
105 3 5 7
106 2 (53)
107 (107)
108 2 3
109 (109)
110 2 5 (11)
111 3 (37)
112 2 7
113 (113)
114 2 3 (19)
115 5 (23)
116 2 (29)
117 3 (13)
118 2 (59)
119 7 (17)
120 2 3 5
121 (11)
122 2 (61)
123 3 (41)
124 2 (31)
125 5

所以获胜者是105和120，每个都有三个质因数；关于并列情况，你需要自行决定该怎么处理。请注意，一些因子被忽略了：11可以整除110和121，13可以整除104和117，17可以整除102和119，19可以整除114，23可以整除115，29可以整除116，31可以整除124，37可以整除111，41可以整除123，53可以整除106，59可以整除118，61可以整除122，当然101、103、107、109和113都是质数。这意味着102、110和114也并列领先，每个都有三个质因数。因此，这个算法并不完美，但对于百位数字范围内的X和Y，并假设您筛选到一百万或一千万的质数，您不太可能错过答案。

好问题。很快在我的博客上发布。

- user448810

---

能否请给我点踩的人解释一下为什么？如果我的回答有问题，我想修正它。 - user448810

Answer 2

从小到大列出所有质数(2,3,5,7...)，开始相乘(2 * 3 * 5 *...)直到得到一个大于等于X的数字P'。如果它小于等于Y，则P = P'。否则，开始计算P'/2、P'/3、P'/5等，寻找[X,Y]范围内的数字。如果找不到并且达到了小于X的数字，请尝试将下一个质数乘入P'并继续。如果仍然失败，则范围[X,Y]非常小，因此退回到在该范围内分解所有数字的方法。

对于一个小范围(Y-X很小)，分配一个大小为Y-X+1的数组，将其设为零，然后对于所有小于等于Y-X的质数，在与该质数的倍数相应的数组元素中添加一(简单筛法)。然后搜索具有最大总和的元素。如果该总和n满足(Y-X)ⁿ >= X，则该值是答案。否则，继续筛选大于Y-X的质数，直到您找到某个质数p，使得表中的某个n满足pⁿ > X...

以上两种方法之一应该有效，具体取决于范围的大小...

- Chris Dodd