Наименьший общий множитель для 3 или более номеров

Question

Как рассчитать наименьшее общее кратное нескольких чисел?

До сих пор мне удавалось рассчитать его только между двумя числами. Но понятия не имею, как его расширить, чтобы вычислить 3 или более числа.

Пока вот как я это сделал

LCM = num1 * num2 /  gcd ( num1 , num2 )

С gcd это функция для вычисления наибольшего общего делителя для чисел. Использование евклидова алгоритма

Но я не могу понять, как рассчитать его для 3 или более чисел.

Answer 1

В питоне:

def lcm(*args):
    """Calculates lcm of args"""
    biggest = max(args) #find the largest of numbers
    rest = [n for n in args if n != biggest] #the list of the numbers without the largest
    factor = 1 #to multiply with the biggest as long as the result is not divisble by all of the numbers in the rest
    while True:
        #check if biggest is divisble by all in the rest:
        ans = False in [(biggest * factor) % n == 0 for n in rest]
        #if so the clm is found break the loop and return it, otherwise increment factor by 1 and try again
        if not ans:
            break
        factor += 1
    biggest *= factor
    return "lcm of {0} is {1}".format(args, biggest)

---

>>> lcm(100,23,98)
'lcm of (100, 23, 98) is 112700'
>>> lcm(*range(1, 20))
'lcm of (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19) is 232792560'

Answer 2

GCD нуждается в небольшой коррекции для отрицательных чисел:

def gcd(x,y):
  while y:
    if y<0:
      x,y=-x,-y
    x,y=y,x % y
    return x

def gcdl(*list):
  return reduce(gcd, *list)

def lcm(x,y):
  return x*y / gcd(x,y)

def lcml(*list):
  return reduce(lcm, *list)

Answer 3

Как насчет этого?

from operator import mul as MULTIPLY

def factors(n):
    f = {} # a dict is necessary to create 'factor : exponent' pairs 
    divisor = 2
    while n > 1:
        while (divisor <= n):
            if n % divisor == 0:
                n /= divisor
                f[divisor] = f.get(divisor, 0) + 1
            else:
                divisor += 1
    return f


def mcm(numbers):
    #numbers is a list of numbers so not restricted to two items
    high_factors = {}
    for n in numbers:
        fn = factors(n)
        for (key, value) in fn.iteritems():
            if high_factors.get(key, 0) < value: # if fact not in dict or < val
                high_factors[key] = value
    return reduce (MULTIPLY, ((k ** v) for k, v in high_factors.items()))

Answer 4

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } int lcm(int[] a, int n) { int res = 1, i; for (i = 0; i < n; i++) { res = res*a[i]/gcd(res, a[i]); } return res; }

Answer 5

clc;

data = [1 2 3 4 5]

LCM=1;

for i=1:1:length(data)

    LCM = lcm(LCM,data(i))

end 

Answer 6

Если нет временных ограничений, это довольно просто и понятно:

def lcm(a,b,c):
    for i in range(max(a,b,c), (a*b*c)+1, max(a,b,c)):
        if i%a == 0 and i%b == 0 and i%c == 0:
            return i

Answer 7

У нас есть рабочая реализация наименьшего общего множителя в Calculla , которая работает для любого количества входов, также отображая шаги.

Что мы делаем:

0: Assume we got inputs[] array, filled with integers. So, for example:
   inputsArray = [6, 15, 25, ...]
   lcm = 1

1: Find minimal prime factor for each input.
   Minimal means for 6 it's 2, for 25 it's 5, for 34 it's 17
   minFactorsArray = []

2: Find lowest from minFactors:
   minFactor = MIN(minFactorsArray)

3: lcm *= minFactor

4: Iterate minFactorsArray and if the factor for given input equals minFactor, then divide the input by it:
  for (inIdx in minFactorsArray)
    if minFactorsArray[inIdx] == minFactor
      inputsArray[inIdx] \= minFactor

5: repeat steps 1-4 until there is nothing to factorize anymore. 
   So, until inputsArray contains only 1-s.

И это все - вы получили свой lcm.

Answer 8

LCM является ассоциативным и коммутативным.

LCM (а, б, в) = LCM (LCM (а, б), в) = LCM (а, LCM (б, в))

вот пример кода в C:

int main()
{
  int a[20],i,n,result=1;  // assumption: count can't exceed 20
  printf("Enter number of numbers to calculate LCM(less than 20):");
  scanf("%d",&n);
  printf("Enter %d  numbers to calculate their LCM :",n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
 for(i=0;i<n;i++)
   result=lcm(result,a[i]);
 printf("LCM of given numbers = %d\n",result);
 return 0;
}

int lcm(int a,int b)
{
  int gcd=gcd_two_numbers(a,b);
  return (a*b)/gcd;
}

int gcd_two_numbers(int a,int b)
{
   int temp;
   if(a>b)
   {
     temp=a;
     a=b;
     b=temp;
   }
  if(b%a==0)
    return a;
  else
    return gcd_two_numbers(b%a,a);
}

Answer 9

для питона 3:

from functools import reduce

gcd = lambda a,b: a if b==0 else gcd(b, a%b)
def lcm(lst):        
    return reduce(lambda x,y: x*y//gcd(x, y), lst)  

Answer 10

Для тех, кто ищет быстрый рабочий код, попробуйте это:

Я написал функцию lcm_n(args, num), которая вычисляет и возвращает lcm всех чисел в массиве args. Второй параметр num - это число чисел в массиве.

Поместите все эти числа в массив args и затем вызовите функцию как lcm_n(args,num);

Эта функция возвращает lcm всех этих чисел.

Вот реализация функции lcm_n(args, num):

int lcm_n(int args[], int num) //lcm of more than 2 numbers
{
    int i, temp[num-1];

    if(num==2)
    {
        return lcm(args[0], args[1]);
    }
    else
    {
        for(i=0;i<num-1;i++)
        {
           temp[i] = args[i];   
        }

        temp[num-2] = lcm(args[num-2], args[num-1]);
        return lcm_n(temp,num-1);
    }
}

Для работы этой функции требуется две функции. Итак, просто добавьте их вместе с ним.

int lcm(int a, int b) //lcm of 2 numbers
{
    return (a*b)/gcd(a,b);
}


int gcd(int a, int b) //gcd of 2 numbers
{
    int numerator, denominator, remainder;

    //Euclid's algorithm for computing GCD of two numbers
    if(a > b)
    {
        numerator = a;
        denominator = b;
    }
    else
    {
        numerator = b;
        denominator = a;
    }
    remainder = numerator % denominator;

    while(remainder != 0)
    {
        numerator   = denominator;
        denominator = remainder;
        remainder   = numerator % denominator;
    }

    return denominator;
}