9

我环顾四周，发现了其他有答案的问题，但没有一个问题涉及这个特定问题的范围。包括这个问题，还有这个。

我必须以有效的方式计算大范围数字的 LCM。我没有对其他问题进行深入研究，因为它们不处理与该算法必须处理的数字一样大的数字范围。

我现在得到的代码可以在大约 90 秒内计算出 1 到 350000 之间每个数字的 LCM。（得到的数字大约有 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？

我不在乎有人建议的算法是否非常占用内存，在这种情况下，时间性能比内存性能更重要（也更昂贵）。

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

问题

计算大量数字的 LCM 的最有效方法是什么？该算法需要在非常广泛的数字范围内运行，因此必须仔细优化。

附录 1

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

4

2 回答 2

3

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

  1. 查找范围内的素数。您可以使用 Eratosthenes 筛子 350000。对于更大的数字范围，您需要分段筛子。

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

为什么是正确的？

  • 对于 p e形式的数字，其中 p 是素数，并且 e >= 1，由于步骤 2，已包含在 LCM 中，因此 p e | 液晶模组。
  • 其他数的形式为 N = p 1 e 1 p 2 e 2 ...p n e n（其中 p i是成对不同的素数，并且 e i >= 1），它大于或等于 p i e i（对于从 1 到 n 的所有 i）。由于 p i e i | LCM，由于前面的论点，N | 液晶模组。
于 2012-08-15T22:04:38.213 回答
2

这是@nhahtdh 答案的概括

第一步，找出所有小于或等于上界的素数。

然后取每个素数 p 并以 p 为基数记下下界和上界。这两个数字中不同的最高数字是您需要包含在 LCM 中的 p 的指数。如果下限为 1，则这与其他答案相同。

请注意，该算法的复杂性不取决于范围的长度，而仅取决于上限的大小。

于 2012-08-15T23:03:27.313 回答