Menos múltiplo comum para 3 ou mais números
https://stackoverflow.com/questions/147515
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como calcular o mínimo múltiplo comum de vários números?
Até agora eu só foi capaz de calculá-lo entre dois números. Mas não têm idéia de como expandi-lo para calcular 3 ou mais números.
Até agora, este é como eu o fiz
LCM = num1 * num2 / gcd ( num1 , num2 )
Com mdc é a função para calcular o máximo divisor comum para os números. Usando Algoritmo de Euclides
Mas eu não consigo descobrir como calculá-lo por 3 ou mais números.
Solução
Você pode calcular o LCM de mais de dois números por iterativa calcular o LCM de dois números, i.
lcm(a,b,c) = lcm(a,lcm(b,c))
Outras dicas
Em Python (modificado 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)
Uso:
>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560
reduce() funciona algo como que :
>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
Aqui está uma implementação 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));
}
}
Eu iria com um presente (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);
}
Apenas alguns esclarecimentos, porque à primeira vista, não parecem ser tão claro o que este código está fazendo:
Aggregate é um método Linq extensão, para que você não pode esquecer de adicionar usando System.Linq para suas referências.
Aggregate recebe uma função de acumular para que possamos fazer uso do LCM propriedade (a, b, c) = lcm (a, lcm (b, c)) ao longo de um IEnumerable. Mais sobre Aggregate
cálculo GCD faz uso do euclidiana algoritmo .
cálculo lcm utiliza Abs (a * b) / GCD (a, b), referem-se a Redução pela maior divisor comum.
Espero que isso ajude,
Eu só descobri isso em 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
Eu mesmo tomou o tempo para escrever minha própria função gcd, apenas para encontrá-lo em Prelude! Lotes de aprendizagem para mim hoje: D
Alguns código Python que não requer uma função 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)
Aqui está o que parece no terminal:
$ python lcm.py 10 15 17
510
Aqui é um Python one-liner (sem contar com as importações) para retornar a LCM dos inteiros de 1 a 20 inclusive:
Python 3.5+ importações:
from functools import reduce
from math import gcd
Python 2.7 importações:
from fractions import gcd
lógica comum:
lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))
Python 2 e Python 3 , regras de precedência do operador ditam que os operadores * e // têm o mesmo precedência, e assim eles se aplicam a partir da esquerda para a direita. Como tal, meios x*y//z (x*y)//z e não x*(y//z). Os dois tipicamente produzir resultados diferentes. Isso não teria importância, tanto para a divisão flutuador, mas ele faz para divisão chão href="https://stackoverflow.com/a/183870/832230">.
Aqui é um C # porto de implemenation de Virgílio 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;
}
}'
Função para encontrar lcm de qualquer lista de números:
def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s
Usando o LINQ você poderia escrever:
static int LCM(int[] numbers)
{
return numbers.Aggregate(LCM);
}
static int LCM(int a, int b)
{
return a * b / GCD(a, b);
}
Se adicionar using System.Linq; e não se esqueça de lidar com as exceções ...
Aqui está em 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) }
}
Você pode fazer isso de outra maneira - Haja n numbers.Take um par de números consecutivos e guardar a sua lcm na outra matriz. Fazendo isso a primeira iteração programa faz n / 2 iterations.Then próxima pegar par a partir de 0, como (0,1), (2,3) e assim a sua on.Compute LCM e armazenar em outra matriz. Faça isso até que você é deixado com uma matriz. (Não é possível encontrar LCM se n for ímpar)
Em R, podemos usar as funções mGCD (x) e MLCM (x) do pacote Números , para calcular o maior divisor comum e menor múltiplo comum para todos os números no vector inteiro 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
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));
}
E a versão 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)
Apenas por diversão, uma concha (quase qualquer shell) implementação:
#!/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"
experimentá-lo com:
$ ./script 2 3 4 5 6
para obter
60
A maior entrada e resultado deve ser inferior a (2^63)-1 ou a matemática shell vai embrulhar.
eu estava procurando GCD e LCM de elementos da matriz e encontrou uma boa solução no seguinte link.
https://www.hackerrank.com/challenges/between-two -sets / forum
que inclui seguinte código. O algoritmo para gcd usa o algoritmo de Euclides explicou bem no link abaixo.
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;
}
Aqui está o PHP aplicação:
// 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
Os créditos vão para @ T3db0t com sua resposta acima (ECMA-style código) .
GCD precisa de um pouco de correção para 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)
Como sobre isso?
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()))
Temos implementação de trabalho do Menor Múltiplo Comum em Calculla que funciona para qualquer número de entradas também exibindo os passos.
O que fazemos é:
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.
E é isso -. Você tem o seu lcm
LCM é tanto associativo e comutativo.
GCV (a, b, c) = LCM (GCV (a, b), c) = GCV (a, LCM (b, c))
aqui é código de exemplo 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);
}
Método compLCM leva um vetor e retorna LCM. Todos os números estão dentro in_numbers vetor.
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++;
}
}
clc;
data = [1 2 3 4 5]
LCM=1;
for i=1:1:length(data)
LCM = lcm(LCM,data(i))
end
Para quem procura código de trabalho rápidos, tente o seguinte:
Eu escrevi uma função lcm_n(args, num) que calcula e retorna a LCM de todos os números na args matriz. A segunda parameternum é a contagem de números na matriz.
Coloque todos esses números em uma args array e, em seguida, chamar a função como lcm_n(args,num);
Esta função retorna LCM de todos esses números.
Aqui está a implementação do lcm_n(args, num) função:
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 função precisa seguir duas funções para o trabalho. Então, basta adicioná-los junto com ele.
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;
}
Em 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'
Isto é o que eu usei -
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
para python 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)
Se não há tempo constrangimento, este é bastante simples e direta:
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
