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

Question

请注意，除数必须唯一

所以 32 有 1 个唯一质因数 [2]，40 有 [2, 5] 等等。

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

我能想到的最好的算法是改进的 Eratosthenes 筛法，它用一个数组计算一个数有多少个质因数。但是不仅是O(n)，这样的范围是不能接受的，而且在内存方面也非常低效。

解决这道题的最佳算法是什么？有这样的算法吗？

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

如现在所写，您需要将 primes 数组预计算到 2³¹，这将是一个包含 105,097,565 个数字的列表 according to Wolfram Alpha.这将导致相当大的内存需求，并且还会使外部循环（其中 productSoFar 仍然很小）迭代大量以后不需要的素数。

您可以做的一件事是更改循环结束条件。除了检查再添加一个质数不会使乘积超过 b，您还可以检查是否可以在不超过 b。如果质因子的总数很大，这将允许您更早地结束循环。

对于少数质因数，事情仍然很棘手。特别是如果你有一个非常窄的范围 [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 位无符号整数）。可以只预先计算那些，并用它来分解范围内的每个数字。但这将再次意味着遍历范围。这对小范围有意义，但对大范围没有意义。

所以也许你需要预先区分这些情况，然后相应地选择算法。我还不知道如何将这些想法结合起来。如果其他人这样做，请随意扩展此 post 或在此基础上编写您自己的答案。

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

How many numbers have a maximum number of unique prime factors in a given range

algorithm

math

prime-factoring