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

Question

请注意，除数必须唯一

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

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

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

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

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 之外，您还可以检查是否可以在乘积中包含下一个 primesToGo 个素数而不超过 >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 位无符号整数)。可以只预先计算那些，并用它来分解范围内的每个数字。但这将再次意味着遍历范围。这对小范围有意义，但对大范围不适用。

因此，您可能需要预先区分这些情况，然后相应地选择算法。我还不知道如何将这些想法结合起来。如果其他人这样做，请随时扩展这篇文章或在此基础上写下您自己的答案。