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

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

138 голосов
/ 29 сентября 2008

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

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

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

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

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

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

Ответы [ 30 ]

170 голосов
/ 29 сентября 2008

Вы можете вычислить LCM из более чем двух чисел, итеративно вычисляя LCM из двух чисел, т.е. 

lcm(a,b,c) = lcm(a,lcm(b,c))
143 голосов
/ 29 сентября 2008

В Python (изменено primes.py ): 

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""   
    return reduce(lcm, args)

Использование: 

>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560

reduce() работает что-то вроде , что : 

>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
23 голосов
/ 15 апреля 2010

Вот реализация в стиле ECMA: 

function gcd(a, b){
    // Euclidean algorithm
    var t;
    while (b != 0){
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

function lcm(a, b){
    return (a * b / gcd(a, b));
}

function lcmm(args){
    // Recursively iterate through pairs of arguments
    // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

    if(args.length == 2){
        return lcm(args[0], args[1]);
    } else {
        var arg0 = args[0];
        args.shift();
        return lcm(arg0, lcmm(args));
    }
}
11 голосов
/ 18 апреля 2015

Я бы пошел с этим (C #): 

static long LCM(long[] numbers)
{
    return numbers.Aggregate(lcm);
}
static long lcm(long a, long b)
{
    return Math.Abs(a * b) / GCD(a, b);
}
static long GCD(long a, long b)
{
    return b == 0 ? a : GCD(b, a % b);
}

Просто некоторые пояснения, потому что на первый взгляд не очень понятно, что делает этот код:

Aggregate - это метод расширения Linq, поэтому вы не можете забыть добавить с помощью System.Linq к своим ссылкам.

Агрегат получает функцию накопления, поэтому мы можем использовать свойство lcm (a, b, c) = lcm (a, lcm (b, c)) над IEnumerable. Подробнее о совокупности

В расчете GCD используется евклидов алгоритм .

* В расчете

lcm используются Abs (a * b) / gcd (a, b), см. Сокращение на наибольший общий делитель .

Надеюсь, это поможет,

6 голосов
/ 07 августа 2012

Некоторый код Python, который не требует функции для gcd: 

from sys import argv 

def lcm(x,y):
    tmp=x
    while (tmp%y)!=0:
        tmp+=x
    return tmp

def lcmm(*args):
    return reduce(lcm,args)

args=map(int,argv[1:])
print lcmm(*args)

Вот как это выглядит в терминале: 

$ python lcm.py 10 15 17
510
6 голосов
/ 27 января 2010

Я только что понял это на Хаскеле: 

lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns

Я даже нашел время, чтобы написать собственную функцию gcd, только чтобы найти ее в Prelude! У меня много знаний сегодня: D

5 голосов
/ 02 ноября 2016

Вот Python с одной строкой (не считая импорт) для возврата LCM целых чисел от 1 до 20 включительно:

Python 3.5+ импортирует: 

from functools import reduce
from math import gcd

Python 2.7 импорт: 

from fractions import gcd

Общая логика: 

lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))

В обоих Python 2 и Python 3 правила приоритета операторов диктуют, что операторы * и // имеют одинаковый приоритет, и поэтому они применяются слева направо , Таким образом, x*y//z означает (x*y)//z, а не x*(y//z). Оба обычно дают разные результаты. Это не имело бы такого большого значения для деления поплавков, но для деления на этаж .

3 голосов
/ 20 ноября 2016

Функция для поиска lcm любого списка чисел: 

 def function(l):
     s = 1
     for i in l:
        s = lcm(i, s)
     return s
3 голосов
/ 06 декабря 2012

Вот порт C # реализации Virgil Disgr4ce: 

public class MathUtils
{
    /// <summary>
    /// Calculates the least common multiple of 2+ numbers.
    /// </summary>
    /// <remarks>
    /// Uses recursion based on lcm(a,b,c) = lcm(a,lcm(b,c)).
    /// Ported from http://stackoverflow.com/a/2641293/420175.
    /// </remarks>
    public static Int64 LCM(IList<Int64> numbers)
    {
        if (numbers.Count < 2)
            throw new ArgumentException("you must pass two or more numbers");
        return LCM(numbers, 0);
    }

    public static Int64 LCM(params Int64[] numbers)
    {
        return LCM((IList<Int64>)numbers);
    }

    private static Int64 LCM(IList<Int64> numbers, int i)
    {
        // Recursively iterate through pairs of arguments
        // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

        if (i + 2 == numbers.Count)
        {
            return LCM(numbers[i], numbers[i+1]);
        }
        else
        {
            return LCM(numbers[i], LCM(numbers, i+1));
        }
    }

    public static Int64 LCM(Int64 a, Int64 b)
    {
        return (a * b / GCD(a, b));
    }

    /// <summary>
    /// Finds the greatest common denominator for 2 numbers.
    /// </summary>
    /// <remarks>
    /// Also from http://stackoverflow.com/a/2641293/420175.
    /// </remarks>
    public static Int64 GCD(Int64 a, Int64 b)
    {
        // Euclidean algorithm
        Int64 t;
        while (b != 0)
        {
            t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}'
2 голосов
/ 24 апреля 2014

Используя LINQ, вы можете написать: 

static int LCM(int[] numbers)
{
    return numbers.Aggregate(LCM);
}

static int LCM(int a, int b)
{
    return a * b / GCD(a, b);
}

Следует добавить using System.Linq; и не забывать обрабатывать исключения ...

Страница:
...