<分区>
X 和 Y 是大于 100 位的整数。找到 [ P , X [ 范围内的整数 Y 并且保证“最佳”素数分解(即具有最独特素数因子的分解)。
我所做的只是检查素数并分解范围内的每个数字，然后找到符合规则的数字。还有其他方法吗？
在上面的例子中，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 .
最佳答案
关于枚举素数的问题的答案总是要找到一种使用筛子解决问题的方法；在您的情况下，您正在寻找具有大量因子的“反素数”数字，但该原则仍然适用。
这个问题的关键在于，对于大多数数字来说，大多数因素都很小。因此，我的建议是为 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，假设你通过素数筛选到一百万或一千万，你不太可能会错过答案。
好问题。很快就会在my blog寻找它.
关于c++ - 分解大于 100 位的整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19282958/