计算一系列数字的最小公倍数的最有效算法是什么？

Question

我环顾四周,找到了其他有问题的答案,但没有一个问题涉及这个问题的范围.包括这个问题,还有这个问题.

我必须以有效的方式计算大范围数字的LCM.我对其他问题看起来并不太深入,因为它们没有处理与此算法必须处理的数字范围一样大的数字范围.

我现在得到的代码可以在大约90秒内计算1到350000之间的每个数字的最小值.(结果数字是大约76000十进制数字).我希望最终能够在数百万甚至数十亿元素的范围内扩展它.

它最终可能会被瘫痪.对于某些算法,这根本不会很难,对于其他算法,它会更棘手(例如,如果算法使用当前生成的LCM来计算其计算的其他部分的素数)

这里是:

public static BigInteger getLCMOfRange(BigInteger lower, BigInteger upper)
{
    BigInteger M = BigInteger.ONE;
    BigInteger t;

    // long l = System.currentTimeMillis();
    // System.out.println("Calculating LCM of numbers up to " + upper + "...");
    for (; lower.compareTo(upper) != 1; lower = lower.add(BigInteger.ONE))
    {
        t = M.gcd(lower);
        if (t.compareTo(lower) == 0)
            continue;
        M = M.multiply(lower).divide(t);
    }
    // System.out.println("Done.  Took " + (System.currentTimeMillis() - l) + " milliseconds.  LCM is " + M.bitCount()+ " bits long.");
    return M;
}

请注意,与典型的for循环不同,此函数在[lower,upper]而不是[lower,upper]上运行.这种行为是故意的.

一些支持数学是一组素数的LCM是一组素数因子的乘积,可以从中产生任何一个数字,而不需要任何外部池.如果我的范围是[1,20],我可以用以下方式表示:

1: 1         6:  3*2      11: 11       16: 2^4
2: 2         7:  7        12: 3*2^2    17: 17
3: 3         8:  2^3      13: 13       18: 3^2*2
4: 2^2       9:  3^2      14: 7*2      19: 19
5: 5         10: 5*2      15: 5*3      20: 5*2^2

LCM{[1,20]}: 2^4*3^2*5*7*11*13*17*19 = 232792560

有没有更有效的方法来在如此大的范围内计算LCM？

我不在乎有人建议的算法是非常大的内存,在这种情况下,时间性能比内存性能更重要(也更昂贵).

这不是一个家庭作业问题.

题

计算大范围数字的最小公倍数的最有效方法是什么？该算法需要在极宽的数字范围内操作,因此必须仔细优化.

附录1

一个密切相关的问题是:计算一个BigInteger(以另一个BigInteger为基数)的对数的最有效方法是什么？结果值可以截断为最接近的整数.

Answer 1

这是算法的布局。我假设你总是从 1 开始：

1. 找出范围内的素数。350000 可以使用埃拉托斯特尼筛。对于更大范围的数字，您需要分段筛。

2. 对于每个素数 p，使用对数函数求 p ^e在范围内的最大指数 e。将 p ^e乘以LCM。（具体优化细节取决于您的实现）

为什么它是正确的？

• ^{对于 p e}形式的数字，其中 p 是素数，并且 e >= 1，由于步骤 2，已包含在 LCM 中，因此 p ^e | 液晶模组。
• 其他数字的形式为 N = p ₁ ^{e ₁} p ₂ ^{e ₂} ...p _n ^{e _n}（其中 p _i是成对不同的素数，并且 e _i >= 1），它大于或等于 p _i ^{e _i}（对于从 1 到 n 的所有 i）。由于 p _i ^{e _i} | LCM，由于之前的争论，N | 液晶模组。