algorithm - 如何从 lcm(a,b) = c 中找到最小的 b？

Question

我知道a和c。我怎样才能找到最少的bif lcm(a,b) = c？

Answer 1

a = m*d, b = n*d, d = gcd(a,b), so c = lcm(a,b) = mnd;  
Thus n = c/a. Notice that the less d, the less b.  
so we can traverse the factor d of a, such that gcd(a/d, n) = 1.
the least d is what we need, then b = n*d.

Answer 2

如果c是lcm(a, b)，c%a=0

然后，

(gcd(a, c/a) * c) / a

给出了答案。

这是从以下事实得出的：lcm(a,b) * gcd(a,b) = a * b

此外，gcd(a,b)通过 euclid 的算法很容易实现，它解决了您的对数复杂性问题。

Answer 3

您可以使用素数分解找到最小公倍数。在这里，lcm(a, b)必须包含它们出现在两个数字中的任何一个中的所有质因数a和它们的最高倍数。b

例如，8 = 2^3和12 = 2^2 * 3，所以lcm(8, 12) = 2^3 * 3 = 24。

这可以很容易地逆转：找到 的主要因素c（包括它们的多重性），然后检查哪些已经被a. b必须是其余的产品。

所以如果c = 24 = 2^3 * 3和a = 6 = 2 * 3，那么b必须是8 = 2^3。3^1已经被覆盖，a但a只有拥有2^1，所以b必须如此2^3。