在给定范围内，有多少个数字具有最大数量的唯一质因数？

Question

请注意，除数必须是唯一的。

因此，32有1个唯一的质因子[2]，40有[2，5]等。

给定一个范围[a，b]，a，b <= 2 ^ 31，我们应该找到在这个范围内有多少个数字具有最大数量的唯一除数。

我能想到的最好算法是改进的埃拉托斯特尼筛选法，使用一个数组来计算数字有多少个质因子。但它不仅是O(n)，在这样的范围内是不能接受的，而且在内存方面也非常低效。 什么是解决这个问题的最佳算法？是否存在这样的算法？

- Denis Rozimovschii

---

最大数量还是特定数量？即因子数量<=某个N；还是因子数量==N？ - user268396

因为如果它是绝对最大值，那么你只需将运行乘积乘以下一个最低的质数，直到超过上限（毕竟，最多的因子意味着每一步中最终产品增加最小，这意味着最小的适用除数）。 - user268396

一个最大数字。 [30，45] 返回2，因为30和42都有3个唯一的质因子。其他数字的质因数较少。 - Denis Rozimovschii

Answer 1

我将用类似Python的伪代码写出第一个想法。首先找出你可能需要的最多质因数：

p = 1
i = 0
while primes[i] * p <= b:
    p = p * primes[i]
    i = i + 1

这只使用了b，而不是a，因此您可能需要减少实际质因数的数量。但由于以上结果最多为9（因为前10个质数的乘积已经超过了2³¹），您可以逐步从这个最大值向下进行：

cnt = 0
while cnt == 0:
    cnt = count(i, 1, 0)
    i = i - 1
return cnt

现在我们需要实现这个函数count，我定义它为递归函数。

def count(numFactorsToGo, productSoFar, nextPrimeIndex):
    if numFactorsToGo > 0:
        cnt = 0
        while productSoFar * primes[nextPrimeIndex] <= b:
            cnt = cnt + count(numFactorsToGo - 1,
                              productSoFar * primes[nextPrimeIndex],
                              nextPrimeIndex + 1)
            nextPrimeIndex = nextPrimeIndex + 1
        return cnt
    else:
        return floor(b / productSoFar) - ceil(a / productSoFar) + 1

这个函数有两种情况需要区分。第一种情况是，您还没有达到所需的质因数数量。因此，您需要乘以另一个质数，该质数必须大于已包含在产品中的最大质数。您可以通过从下一个质数的给定索引开始来实现这一点。您需要将所有这些递归调用的计数相加。

第二种情况是已经达到所需的质因数数量。在这种情况下，您要计算所有可能的整数k，使得a ≤ k∙p ≤ b。这很容易转化为⌈a/p⌉ ≤ k ≤ ⌊b/p⌋，因此计数将为⌊b/p⌋ − ⌈a/p⌉ + 1。在实际实现中，我不会使用浮点除法和floor或ceil，而是为了性能而使用截断整数除法。因此，我可能会将这一行写成：

        return (b // productSoFar) - ((a - 1) // productSoFar + 1) + 1

现在的写法需要预先计算出2的31次方以内的质数数组，这将是一个包含105097565个数字的列表根据Wolfram Alpha。这将导致相当大的内存需求，并且使外部循环（其中productSoFar仍然很小）迭代许多以后不再需要的质数。

你可以做的一件事是改变循环结束条件。不仅要检查添加一个质数是否会使产品超过b，而且还要检查是否可以在不超过b的情况下将接下来的primesToGo个质数包含在产品中。如果质因数的总数很大，这将允许您更早地结束循环。

对于一些小的质因数，问题仍然很棘手。特别是如果你有一个非常狭窄的范围[a, b]，那么具有最大质因数计数的数字很可能是一个大的质因数乘以一系列非常小的质因数的积。例如考虑[2147482781, 2147482793]。这个区间包含4个具有4个不同因子的元素，其中一些包含相当大的质因数，即

• 3 ∙ 5 ∙ 7 ∙ 20,452,217
• 2² ∙ 3 ∙ 11 ∙ 16,268,809
• 2 ∙ 5 ∙ 19 ∙ 11,302,541
• 2³ ∙ 7 ∙ 13 ∙ 2,949,839

由于sqrt(2³¹)以下只有4,792个质数，其中最大的为46,337（适合于16位无符号整数），因此可以预先计算它们，并用它们来分解范围内的每个数字。但这又意味着要迭代整个范围。这在小范围内是有意义的，但对于大范围则不然。

也许你需要事先区分这些情况，然后相应地选择算法。我还不知道如何将这些想法结合起来。如果有人知道，请随意扩展此文章或在此基础上撰写自己的答案。

- MvG