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

minimo comun multiplo y maximo comun divisor aritmetica

Question

¿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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

Aquí está la implementación de PHP :

 // https://.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://.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

Los créditos van a @T3db0t con su respuesta anterior (código de estilo ECMA) .

Answer 5

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 .

Answer 6

Aquí hay un puerto C # de la implementación de 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://.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://.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;
}
}''

Answer 7

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

Answer 8

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<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 9

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)

Answer 10

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''

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Esto es lo que usé -

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

Answer 15

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

Answer 16

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)

Answer 17

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

Me di cuenta de esto en Haskell:

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

¡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

Answer 19

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,

Answer 20

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<num-1;i++)
{
temp[i] = args[i];
}
temp[num-2] = lcm(args[num-2], args[num-1]);
return lcm_n(temp,num-1);
}
}

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

Answer 21

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

Answer 22

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.

Answer 23

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.

Answer 24

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 ...

Answer 25

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)

Answer 26

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

Answer 27

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 28

clc;
data = [1 2 3 4 5]
LCM=1;
for i=1:1:length(data)
LCM = lcm(LCM,data(i))
end