数论算法。区间内最多的因数

Question

我正在寻找一种高效的算法来解决以下问题。设d(n)表示正整数n的正因数个数。给定一些1 <= a <= b <= 10^18，任务是在区间[a..b]上找到最大的d值，并且（可能需要更复杂的算法）找到使d值最大化的数字。

不久前我在免费资源中发现了以下代码：http://ideone.com/qvxPj

unsigned long long n, res;
int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};

unsigned long long mul(unsigned long long a, unsigned long long b){
    unsigned long long res = 0;

    while (b){
        if (b & 1LL) res = (res + a);
        if (res >= n) return 0;
        a = (a << 1LL);
        b >>= 1LL;
    }

    return res;
}

void backtrack(int i, int lim, unsigned long long val, unsigned long long r){
    if (r > res) res = r;
    if (i == p) return;

    int d;
    unsigned long long x = val;

    for (d = 1; d <= lim; d++){
        x = mul(x, primes[i]);
        if (x == 0) return;
        backtrack(i + 1, d, x, r * (d + 1));
    }
}

int main(){    
    p = sizeof(primes) / sizeof(int);

    while (scanf("%llu", &n) != EOF){
        res = 0;
        backtrack(0, 100, 1, 1);
        printf("Maximum number of divisors of any number less than %llu = %llu\n", n, res);
    }
    return 0;
}

如果有人能够解释它的工作原理，我会非常高兴，因为（对我来说）这个程序运行得非常快。

先感谢任何帮助。

- Igor

---

请修复代码环境：在 mul 函数之前添加一个空行。 - stgatilov

你是否考虑不同的因子？因子是否需要是简单的？例如，d(12)会是多少？ - Dmitry Grigoryev

我考虑所有的除数，因此d(1) = 1，d(prime) = 2，d(12) = 6。 - Igor

Answer 1

它会像这样遍历所有数字：

num = P1^D1 * P2^D2 * P3^D3 * ... * Ps^Ds
constraints:
  Pi <= 71
  1 <= Di <= 100
  sequence (Pi) is a sorted list of first s primes
  sequence (Di) is nonincreasing
  num <= n

让我们先检查第一个限制条件。假设最小的最优数具有质因子q>71 。如果任何质数p≤71 在此数字中未使用，则我们可以用相同的次数将q 替换为p 。显然，约数的数量将保持不变，但数字会减少 -> 矛盾。然后没有未使用的小于71的质数。但是，所有小于71的质数的乘积已经非常巨大，我们考虑的数字必须大于64位的n 。这是不可能的。

现在让我们解释第二个和第三个限制条件。假设我们的最小最优数在其因式分解中有一个质数q ，但缺少一些质数p ，其中p＜q 。那么我们可以用相同的顺序将q 替换为p ，数字将具有相同数量的约数，但它将变小 -> 矛盾。这意味着所找到的最优（最小）数的所有质数的因式分解必须正好是前s个质数。使用的质数集中不能有空洞。BTW，Di≤100 是显而易见的，因为即使2 ^ 100也不适合64位整数。

现在我们必须解释第四个约束条件。假设D [i]＜D [i + 1] 对于某些i 成立。然后我们可以用P [i] ^ D [i + 1] * P [i + 1] ^ D [i] 替换P [i] ^ D [i] * P [i + 1] ^ D [i + 1] ，数字会变小。例如，使用5 ^ 3 * 7 ^ 2替换5 ^ 2 * 7 ^ 3：约数数量相同，但结果更小。显然，如果我们搜索最小的最优数，我们也可以安全地假定此条件。

现在让我们考虑代码。 mul 是一个小函数，计算a 和b 的乘积。它通过有趣的二进制过程计算。这个过程的主要原因是：如果乘积大于n ，则函数返回0。该程序仅是防止溢出的保护措施，否则可能会发生溢出。

最后，我们到达了backtrack 。这是一个通常的递归搜索。 val 是当前数字，r 是其约数的数量，i 显示我们现在要添加的质数的索引，lim 将每个质数的幂限制为100。一开始你会看到当前最优答案（存储在res 中）的更新以及硬停止条件（使用所有质数）。

接下来是一个循环，检查当前素数的每个幂次。它从幂次1开始，因为禁止零次幂。它将当前数字保存在x中，并在每次迭代中乘以Pi来增加幂次。如果x大于n，则立即停止。最后，它调用自身以搜索下一个素数。

- stgatilov

Answer 2

作为对@stgatilov答案的补充，我将证明限制质数小于或等于71的选择。

我使用了一个稍微修改过的代码来记录具有最大除数数量的最大数字。 对于1000000000000000000或999999999999999999，我得到：

897612484786617600 = 2 ^ 8 * 3 ^ 4 * 5 ^ 2 * 7 ^ 2 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37

共有103680个约数。

这意味着对于所有18位十进制数字，没有大于37的质数涉及找到具有最多约数的整数。

- Serge Ballesta