Как найти наименьшее b из lcm (a, b) = c?

Question

Я знаю a и c.Как мне найти наименьшее значение b, если lcm(a,b) = c?

Answer 1

Вы можете найти наименьшее общее кратное, используя простое разложение .Здесь 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.

Answer 2

Если c равно lcm(a, b), c%a=0

Тогда,

if gcd(a, c/a) == 1:
    b = c/a
else
    b = c

Answer 3

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.