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

Question

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

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

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

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

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

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

Answer 1

Вот оно в Свифт .

// Euclid's algorithm for finding the greatest common divisor
func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

// Returns the least common multiple of two numbers.
func lcm(_ m: Int, _ n: Int) -> Int {
  return m / gcd(m, n) * n
}

// Returns the least common multiple of multiple numbers.
func lcmm(_ numbers: [Int]) -> Int {
  return numbers.reduce(1) { lcm($0, $1) }
}

Answer 2

ES6 стиль

function gcd(...numbers) {
  return numbers.reduce((a, b) => b === 0 ? a : gcd(b, a % b));
}

function lcm(...numbers) {
  return numbers.reduce((a, b) => Math.abs(a * b) / gcd(a, b));
}

Answer 3

вы можете сделать это по-другому - Пусть будет n чисел. Возьмите пару последовательных чисел и сохраните их lcm в другом массиве. Делая это на первой итерации, программа делает n / 2 итерации. Затем берется следующая пара, начиная с 0, например (0,1), (2,3) и т. Д. Вычислите их LCM и сохраните в другом массиве. Делайте это, пока у вас не останется один массив. (невозможно найти lcm, если n нечетно)

Answer 4

Вот реализация PHP :

    // https://stackoverflow.com/q/12412782/1066234
    function math_gcd($a,$b) 
    {
        $a = abs($a); 
        $b = abs($b);
        if($a < $b) 
        {
            list($b,$a) = array($a,$b); 
        }
        if($b == 0) 
        {
            return $a;      
        }
        $r = $a % $b;
        while($r > 0) 
        {
            $a = $b;
            $b = $r;
            $r = $a % $b;
        }
        return $b;
    }

    function math_lcm($a, $b)
    {
        return ($a * $b / math_gcd($a, $b));
    }

    // https://stackoverflow.com/a/2641293/1066234
    function math_lcmm($args)
    {
        // Recursively iterate through pairs of arguments
        // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

        if(count($args) == 2)
        {
            return math_lcm($args[0], $args[1]);
        }
        else 
        {
            $arg0 = $args[0];
            array_shift($args);
            return math_lcm($arg0, math_lcmm($args));
        }
    }

    // fraction bonus
    function math_fraction_simplify($num, $den) 
    {
        $g = math_gcd($num, $den);
        return array($num/$g, $den/$g);
    }


    var_dump( math_lcmm( array(4, 7) ) ); // 28
    var_dump( math_lcmm( array(5, 25) ) ); // 25
    var_dump( math_lcmm( array(3, 4, 12, 36) ) ); // 36
    var_dump( math_lcmm( array(3, 4, 7, 12, 36) ) ); // 252

Кредиты отправляются на @ T3db0t с ответом выше (код в стиле ECMA) .

Answer 5

Я искал gcd и lcm элементов массива и нашел хорошее решение по следующей ссылке.

https://www.hackerrank.com/challenges/between-two-sets/forum

, который включает следующий код. Алгоритм для gcd использует Евклидов алгоритм, объясненный в ссылке ниже.

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

private static int gcd(int a, int b) {
    while (b > 0) {
        int temp = b;
        b = a % b; // % is remainder
        a = temp;
    }
    return a;
}

private static int gcd(int[] input) {
    int result = input[0];
    for (int i = 1; i < input.length; i++) {
        result = gcd(result, input[i]);
    }
    return result;
}

private static int lcm(int a, int b) {
    return a * (b / gcd(a, b));
}

private static int lcm(int[] input) {
    int result = input[0];
    for (int i = 1; i < input.length; i++) {
        result = lcm(result, input[i]);
    }
    return result;
}

Answer 6

Просто для удовольствия, реализация оболочки (почти любой оболочки):

#!/bin/sh
gcd() {   # Calculate $1 % $2 until $2 becomes zero.
      until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
      echo "$1"
      }

lcm() {   echo "$(( $1 / $(gcd "$1" "$2") * $2 ))";   }

while [ $# -gt 1 ]; do
    t="$(lcm "$1" "$2")"
    shift 2
    set -- "$t" "$@"
done
echo "$1"

попробуйте с:

$ ./script 2 3 4 5 6

чтобы получить

60

Наибольший ввод и результат должны быть меньше (2^63)-1, иначе вычислится математика оболочки.

Answer 7

И версия Scala:

def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
def gcd(nums: Iterable[Int]): Int = nums.reduce(gcd)
def lcm(a: Int, b: Int): Int = if (a == 0 || b == 0) 0 else a * b / gcd(a, b)
def lcm(nums: Iterable[Int]): Int = nums.reduce(lcm)

Answer 8

В R мы можем использовать функции mGCD (x) и mLCM (x) из пакета чисел , чтобы вычислить наибольший общий делитель и наименьшее общее кратное для всех чисел в целочисленном векторе x вместе:

    library(numbers)
    mGCD(c(4, 8, 12, 16, 20))
[1] 4
    mLCM(c(8,9,21))
[1] 504
    # Sequences
    mLCM(1:20)
[1] 232792560

Answer 9

Метод compLCM берет вектор и возвращает LCM. Все числа находятся внутри вектора in_numbers.

int mathOps::compLCM(std::vector<int> &in_numbers)
 {
    int tmpNumbers = in_numbers.size();
    int tmpMax = *max_element(in_numbers.begin(), in_numbers.end());
    bool tmpNotDividable = false;

    while (true)
    {
        for (int i = 0; i < tmpNumbers && tmpNotDividable == false; i++)
        {
            if (tmpMax % in_numbers[i] != 0 )
                tmpNotDividable = true;
        }

        if (tmpNotDividable == false)
            return tmpMax;
        else
            tmpMax++;
    }
}

Answer 10

Это то, что я использовал -

def greater(n):

      a=num[0]

      for i in range(0,len(n),1):
       if(a<n[i]):
        a=n[i]
      return a

r=input('enter limit')

num=[]

for x in range (0,r,1):

    a=input('enter number ')
    num.append(a)
a= greater(num)

i=0

while True:

    while (a%num[i]==0):
        i=i+1
        if(i==len(num)):
               break
    if i==len(num):
        print 'L.C.M = ',a
        break
    else:
        a=a+1
        i=0