给定一组数字，找出其中LCM（最小公倍数）最小的一对数字。

Question

我采用了以下方法。

1. 找到n个数字的所有可能的nC2对。
2. 然后通过计算它们的GCD并将两个数字的积除以GCD分别找到它们的LCM。
3. 还维护了一个变量，其中包含到目前为止计算的最小LCM值，并最终输出它。

但是，当数字值非常大（约为10^9）时，这种天真的方法似乎效率低下，因为GCD的时间复杂度取决于数字的大小。此外，对于非常大的N值，这也是不可行的。 有没有其他更好的方法来解决这个问题？

- Krishna Bagaria

---

n的最大范围是多少？ - Kaidul

@Kaidul N的约束条件为2 <= N <= 1000。 - Krishna Bagaria

分解质因数对最小公倍数有什么影响？排序会有帮助吗？ - greybeard

Answer 1

我认为这个问题没有一个高效的算法。

你总是可以使用启发式和简单的方法来解决这个问题。

对于大多数数组来说，平均而言，数字对将会像a,b(a<b)，其中LCM(a,b) ~ O(b)，即a的大部分因子都包含在b中，因此LCM将近似于O(b)。

因此，平均而言，LCM不会很大，类似于数组元素。

所以，想法是先按升序排序数组，然后从小的a,b开始尝试。当b > lcm_so_far时。

谢谢

- v78

---

我不理解“当b > lcm_so_far时，会发生什么？”（不确定“启发式和简单一定有效”的问题。） - greybeard

Answer 2

对于大量数字，我认为一个高效的欧几里得算法实现（https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency）来寻找最大公约数是我能想到的最佳方法。没有快速通用的分解主因数的算法，因此使用它来减少问题不会帮助运行时间。我不知道有任何快速缩小范围的方法可以帮助解决这个问题。

针对大 N，我认为这就是其他人所说的：

1. 对数组进行排序 2. 从最小值开始计算最小公倍数（例如使用欧几里得算法计算最大公约数），并使用短路：一旦剩余配对的LCM不能小于迄今为止找到的最佳值，则停止处理。请注意，在排序集合中，对于两个数字b和c，b < c，LCM的下界是(b * c) / b = c（当b整除c时发生）。请参见以下工作代码（short_lcm版本）。 还有其他优化可以应用于此（例如不要在Python中编写它:)），但这证明了算法的改进。

import fractions

def lcm(a, b):
    return abs(a * b) / fractions.gcd(a, b)

def short_lcm(a):
    a = sorted(a)

    iterations = 0
    cur_lcm = lcm(a[0], a[1])
    first = a[0]
    second = a[1]
    for i in range(0, len(a)):
        #Best case for remaining pairs
        if i < len(a) - 1 and a[i + 1] >= cur_lcm: break

        for j in range(i + 1, len(a)): #Starting at i + 1 avoids duplicates
            if a[j] >= cur_lcm: break  #Best case for remaining pairs

            iterations += 1

            test = lcm(a[i], a[j])
            if test < cur_lcm:
                cur_lcm = test
                first = a[i]
                second = a[j]

    if iterations < 1: iterations = 1

    print("Lowest LCM pair is (%d, %d): %d. Found in %d iterations" % (
                first, second, cur_lcm, iterations))

def long_lcm(a):
    iterations = 0
    cur_lcm = lcm(a[0], a[1])
    first = a[0]
    second = a[1]
    for i in range(0, len(a)):
        for j in range(i + 1, len(a)):     #Starting at i + 1 avoids duplicates
            iterations += 1

             test = lcm(a[i], a[j])
            if test < cur_lcm:
                cur_lcm = test
                first = a[i]
                second = a[j]

    print("Lowest LCM pair is (%d, %d): %d. Found in %d iterations" % (
                first, second, cur_lcm, iterations))

if __name__ == '__main__':
    from random import randint
    import time

    a = [randint(1, 1000) for r in xrange(100)]

    #Only print the list if it's relatively short
    if len(a) < 20: print a

    #Try all pairs
    start = time.clock()
    long_lcm(a)
    print "Slow version time: %f\n" % (time.clock() - start)

    start = time.clock()
    short_lcm(a)
    print "Fast version time: %f" % (time.clock() - start)

- Andrew

---

嘿，安德鲁。你能说一下这个程序还有哪些改进可以做吗？ - Deepak Tatyaji Ahire