Mínimo múltiplo común para 3 o más números

¿Cómo se calcula el mínimo común múltiplo de varios números?

Hasta ahora solo he podido calcularlo entre dos números. Pero no tengo idea de cómo expandirlo para calcular 3 o más números.

Hasta ahora, así es como lo hice

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

Con gcd es la función para calcular el mayor divisor común para los números. Usando algoritmo euclidiano

Pero no puedo descifrar cómo calcularlo para 3 o más números.

Puede calcular el LCM de más de dos números calculando iterativamente el LCM de dos números, es decir,

 lcm(a,b,c) = lcm(a,lcm(b,c)) 

En Python ( primes.py modificado):

 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) 

Uso:

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

reduce() funciona algo así:

 >>> f = lambda a,b: "f(%s,%s)" % (a,b) >>> print reduce(f, "abcd") f(f(f(a,b),c),d) 

Aquí hay una implementación de estilo 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 // ie 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)); } } 

Me gustaría ir con este (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); } 

Solo algunas aclaraciones, porque a primera vista no parece tan claro lo que está haciendo este código:

El agregado es un método de extensión de Linq, por lo que no puede olvidar agregar System.Linq a sus referencias.

El agregado obtiene una función de acumulación para que podamos hacer uso de la propiedad lcm (a, b, c) = lcm (a, lcm (b, c)) sobre un IEnumerable. Más sobre el agregado

El cálculo de GCD utiliza el algoritmo euclidiano .

El cálculo de lcm usa Abs (a * b) / gcd (a, b), consulte Reducción por el mayor divisor común .

Espero que esto ayude,

Me di cuenta de esto en Haskell:

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

¡Incluso me tomé el tiempo de escribir mi propia función gcd , solo para encontrarla en Preludio! Un montón de aprendizaje para mí hoy: D

Algunos códigos de Python que no requieren una función para 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) 

Esto es lo que parece en la terminal:

 $ python lcm.py 10 15 17 510 

Aquí hay un Python one-liner (sin contar las importaciones) para devolver el LCM de los enteros del 1 al 20 inclusive:

Python 3.5+ importaciones:

 from functools import reduce from math import gcd 

Importaciones de Python 2.7:

 from fractions import gcd 

Lógica común:

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

Tanto en Python 2 como en Python 3 , las reglas de precedencia del operador dictan que los operadores * y // tengan la misma precedencia, por lo que se aplican de izquierda a derecha. Como tal, x*y//z significa (x*y)//z y no x*(y//z) . Los dos típicamente producen diferentes resultados. Esto no habría importado tanto para la división de flotación, pero sí para la división de piso .

Aquí hay un puerto C # de la implementación de Virgil Disgr4ce:

 public class MathUtils { ///  /// Calculates the least common multiple of 2+ numbers. ///  ///  /// Uses recursion based on lcm(a,b,c) = lcm(a,lcm(b,c)). /// Ported from http://stackoverflow.com/a/2641293/420175. ///  public static Int64 LCM(IList 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)numbers); } private static Int64 LCM(IList numbers, int i) { // Recursively iterate through pairs of arguments // ie 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)); } ///  /// Finds the greatest common denominator for 2 numbers. ///  ///  /// Also from http://stackoverflow.com/a/2641293/420175. ///  public static Int64 GCD(Int64 a, Int64 b) { // Euclidean algorithm Int64 t; while (b != 0) { t = b; b = a % b; a = t; } return a; } }' 

Función para encontrar lcm de cualquier lista de números:

  def function(l): s = 1 for i in l: s = lcm(i, s) return s 

Usando LINQ puedes escribir:

 static int LCM(int[] numbers) { return numbers.Aggregate(LCM); } static int LCM(int a, int b) { return a * b / GCD(a, b); } 

Debería agregar using System.Linq; y no te olvides de manejar las excepciones …

puedes hacerlo de otra manera: permite que haya n números. Toma un par de números consecutivos y guarda su lcm en otra matriz. Al hacer esto en el primer progtwig de iteración, se realizan n / 2 iteraciones. A continuación, seleccione el par empezando desde 0 como (0,1), (2,3) y así sucesivamente. Calcule su LCM y almacénelo en otra matriz. Haga esto hasta que se quede con una matriz. (no es posible encontrar lcm si n es impar)

En R, podemos usar las funciones mGCD (x) y mLCM (x) a partir de los números de paquete, para calcular el mayor divisor común y el mínimo múltiplo común para todos los números en el vector entero x juntos:

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

Y la versión de 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) 

Solo por diversión, una implementación de shell (casi cualquier shell):

 #!/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" 

Pruébalo con:

 $ ./script 2 3 4 5 6 

Llegar

 60 

La entrada y el resultado más grandes deben ser menores que (2^63)-1 o las operaciones de shell se ajustarán.

Estaba buscando gcd y lcm de elementos de matriz y encontré una buena solución en el siguiente enlace.

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

que incluye el siguiente código. El algoritmo para usos de gcd El algoritmo euclidiano se explica bien en el siguiente enlace.

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; } 

Aquí está en Swift .

 // 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) } } 

GCD necesita una pequeña corrección para los números negativos:

 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) 

¿Qué tal esto?

 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())) 

Tenemos la implementación de trabajo de Least Common Multiple en Calculla que funciona para cualquier cantidad de entradas que también muestren los pasos.

Lo que hacemos es:

 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. 

Y eso es todo, tienes tu lcm.

LCM es tanto asociativo como conmutativo.

LCM (a, b, c) = LCM (LCM (a, b), c) = LCM (a, LCM (b, c))

aquí hay un código de muestra en 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;ib) { temp=a; a=b; b=temp; } if(b%a==0) return a; else return gcd_two_numbers(b%a,a); } 

El método compLCM toma un vector y devuelve LCM. Todos los números están dentro del vector en números.

 int mathOps::compLCM(std::vector &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++; } } 

Estilo 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)); } 
 clc; data = [1 2 3 4 5] LCM=1; for i=1:1:length(data) LCM = lcm(LCM,data(i)) end 

Para cualquiera que busque un código de trabajo rápido, intente esto:

Escribí una función lcm_n(args, num) que calcula y devuelve el lcm de todos los números en el array args . El segundo parámetro num es el recuento de números en la matriz.

Pon todos esos números en un array args y luego llama a la función como lcm_n(args,num);

Esta función devuelve el lcm de todos esos números.

Aquí está la implementación de la función 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 

Esta función necesita menos de dos funciones para funcionar. Entonces, simplemente agrégalos junto con eso.

 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; } 

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; }

En Python:

 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' 

Esto es lo que usé –

 def greater(n): a=num[0] for i in range(0,len(n),1): if(a