4

X并且Y是大于 100 位的整数。找到在[ , [P范围内并保证“最佳”素数分解(即具有最独特素数因子的分解)内的整数。XY

我所做的只是检查素数并分解范围内的每个数字并找到符合规则的数字。有没有其他方法可以做到这一点?

一个小整数的例子

编辑:

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

而答案 123690 被分解为 6 ​​个独特的因素
2^1 * 3^1 * 5^1 * 7^1 * 19^1 * 31^1

4

2 回答 2

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,假设你按质数筛选到一百万或一千万,你不太可能错过答案。

好问题。很快在我的博客上寻找它。

于 2013-10-10T00:47:05.650 回答
1

按顺序 (2,3,5,7...) 取出所有素数的列表并开始将它们相乘 (2 * 3 * 5 *...) 直到得到一个 >= X 的数。称这个数为 P'。如果它 <= Y,你就完成了,P = P'。如果不是,则开始计算 P'/2、P'/3、P'/5 等以查找数字 [X,Y]。如果你没有找到它并得到一个 < X 的数字,请尝试将下一个素数乘以 P' 并继续。如果这仍然失败,则范围 [X,Y] 非常小,所以退回到分解该范围内所有数字的方法。

对于一个小范围(YX 很小),分配一个大小为 Y-X+1 的数组,将其归零,然后对于所有素数 <= YX,将对应于素数倍数的数组元素加一(简单 seive)。然后搜索总数最大的元素。如果总 n 满足 (YX) n >= X,那么这就是答案。如果不是,继续筛选大于 YX 的素数,直到找到某个素数 p,使得对于表中的某些 n,p n > X...

上述两种方法中的一种应该可以工作,具体取决于范围有多大......

于 2014-02-07T00:15:31.623 回答