Multiple le moins commun pour 3 nombres ou plus

comment calculer le multiple de numéros Le moins courant?

jusqu'à présent, je n'ai pu le calculer qu'entre deux nombres. Mais n'ont aucune idée de la façon de l'étendre pour calculer 3 nombres ou plus.

jusqu'à présent, c'est la façon dont je l'ai fait

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

Avec pgcd est la fonction pour calculer le plus grand diviseur commun des nombres. Utilisation de l'algorithme euclidien

mais je n'arrive pas à comprendre comment le calculer pour 3 numéros ou plus.

135
demandé sur Kip 2008-09-29 08:33:16

30 réponses

vous pouvez calculer la CML de plus de deux nombres en calculant itérativement la CML de deux nombres, i.e.

lcm(a,b,c) = lcm(a,lcm(b,c))
167
répondu A. Rex 2008-09-29 04:37:31

en Python (modifié 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)

Utilisation:

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

reduce() fonctionne quelque chose comme que :

>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
140
répondu jfs 2016-11-01 23:06:29

Voici un ECMA-mise en œuvre de style:

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));
    }
}
20
répondu T3db0t 2010-04-14 21:48:38

je voudrais aller avec celui-ci (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);
}

juste quelques clarifications, parce qu'à première vue, il ne se confond pas si clairement ce que ce code fait:

Aggregate est une méthode D'Extension Linq, donc vous ne pouvez pas oublier d'ajouter en utilisant le système.Linq à vos références.

Globale obtient une accumulation de fonction de sorte que nous pouvons faire usage de la propriété ppcm(a,b,c) = ppcm(a,ppcm(b,c)) sur un IEnumerable. plus sur Total

PGCD de calcul rend l'utilisation de la algorithme d'Euclide .

lcm calcul utilise Abs(a*b)/pgcd(a,b) , reportez-vous à la Réduction par le plus grand commun diviseur .

Espère que cette aide,

9
répondu Rodrigo López 2015-04-20 02:23:25

je viens de le découvrir à 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

j'ai même pris le temps d'écrire ma propre fonction gcd , pour la trouver en prélude! Beaucoup d'apprentissage pour moi aujourd'hui :D

6
répondu Matt Ellen 2010-01-28 10:13:27

un code Python qui ne nécessite pas de fonction pour 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)

voici à quoi il ressemble dans le terminal:

$ python lcm.py 10 15 17
510
6
répondu Eratosthenes 2012-08-07 17:54:27

voici un Python one-liner (sans compter les importations) pour retourner le CML des entiers de 1 à 20 inclus:

Python 3.5+ importations:

from functools import reduce
from math import gcd

Python 2.7 importations:

from fractions import gcd

logique commune:

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

Dans les deux Python 2 et Python 3 , la priorité de l'opérateur règles exigent que la * et // les opérateurs ont la même priorité, et ils s'appliquent donc de gauche à droite. À ce titre, x*y//z signifie (x*y)//z et non x*(y//z) . Les deux donnent généralement des résultats différents. Cela n'aurait pas eu autant d'importance pour la division float, mais c'est le cas pour la floor division .

5
répondu A-B-B 2018-03-27 14:12:47

voici un C # port de la mise en œuvre 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://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;
    }
}'
3
répondu t9mike 2012-12-05 20:26:29

fonction pour trouver lcm de n'importe quelle liste de numéros:

 def function(l):
     s = 1
     for i in l:
        s = lcm(i, s)
     return s
3
répondu Aaditya Mishra 2016-11-30 16:29:46

en utilisant LINQ vous pouvez écrire:

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

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

Devrait ajouter using System.Linq; et n'oubliez pas de gérer les exceptions ...

2
répondu SepehrM 2014-04-24 12:27:31

vous pouvez le faire d'une autre manière - Qu'il y ait des n nombres.Prenez une paire de nombres consécutifs et sauvegardez son lcm dans un autre tableau. Faire cela à la première itération programme fait n/2 itérations.Puis ramassez la paire suivante à partir de 0 comme (0,1) , (2,3) et ainsi de suite.Calculer leur CML et stocker dans un autre tableau. Faites ceci jusqu'à ce qu'il vous reste un tableau. (il n'est pas possible de trouver la MCP si n est impair)

1
répondu mohit 2012-08-04 00:01:55

dans R, Nous pouvons utiliser les fonctions mgmd (x) et mLCM (x) du paquet nombres , pour calculer le plus grand diviseur commun et le moins commun multiple pour tous les nombres dans le vecteur entier x Ensemble:

    library(numbers)
    mGCD(c(4, 8, 12, 16, 20))
[1] 4
    mLCM(c(8,9,21))
[1] 504
    # Sequences
    mLCM(1:20)
[1] 232792560
1
répondu mpalanco 2015-04-05 15:15:35

et la version 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)
1
répondu Zach-M 2016-11-14 19:09:59

Juste pour le fun, un shell (presque n'importe quel shell) mise en œuvre:

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

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

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

essayer avec:

$ ./script 2 3 4 5 6

pour obtenir

60

la plus grande entrée et le résultat devrait être moins que (2^63)-1 ou le calcul shell enveloppera.

1
répondu sorontar 2016-11-25 01:06:28

je cherchais gcd et lcm d'éléments de réseau et j'ai trouvé une bonne solution dans le lien suivant.

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

qui comprend le code suivant. L'algorithme de pgcd utilise L'Algorithme d'Euclide bien expliqué dans le lien ci-dessous.

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;
}
1
répondu mehmet riza oz 2016-12-26 13:21:22

Ici, il 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("151900920", ) }
}
1
répondu cmilr 2018-03-24 16:42:04

PGCD besoin d'un peu de correction pour les nombres négatifs:

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)
0
répondu Roger Garzon Nieto 2013-01-04 18:08:44

et ça?

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()))
0
répondu Alessandro Martin 2013-05-30 02:53:00

nous avons l'implémentation de travail du Multiple Le moins commun sur le calcul qui fonctionne pour un nombre quelconque d'entrées affichant également les étapes.

Ce que nous faisons est la suivante:

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.

et c'est tout - vous avez votre lcm.

0
répondu yosh kemu 2015-02-05 16:26:47

LCM est à la fois associatif et commutatif.

CML (a,b,c)=CML(CML (a,b),c)=CML(a, CML (b, c))

voici un exemple de code 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);
}
0
répondu User 2015-02-23 05:16:26

méthode compLCM prend un vecteur et renvoie LCM. Tous les nombres se trouvent dans vector 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++;
    }
}
0
répondu Behnam Dezfouli 2015-04-30 21:05:04

ES6 style

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));
}
0
répondu Saebekassebil 2015-05-28 08:24:43
clc;

data = [1 2 3 4 5]

LCM=1;

for i=1:1:length(data)

    LCM = lcm(LCM,data(i))

end 
0
répondu MD Nashid Anjum 2015-06-07 11:56:40

pour tous ceux qui cherchent un code de travail rapide, essayez ceci:

j'ai écrit une fonction lcm_n(args, num) qui calcule et renvoie le CML de tous les nombres dans le tableau args . Le second paramètre num est le nombre de nombres dans le tableau.

mettez tous ces numéros dans un tableau args et appelez la fonction comme lcm_n(args,num);

cette fonction retourne le lcm de tous ces numéros.

Voici la mise en œuvre de la fonction 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);
    }
}

cette fonction nécessite moins de deux fonctions pour fonctionner. Donc, il suffit de les ajouter avec elle.

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;
}
0
répondu Nikhil 2016-01-07 17:55:18

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

0
répondu vipul 2016-09-15 15:51:35

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'
0
répondu ateymuri 2016-12-25 13:50:42

C'est ce que j'ai utilisé --

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
0
répondu Vishwajeet Gaur 2017-02-16 20:58:32

voici le PHP implémentation:

     // /q/simplifier une fraction-45205/"https://stackoverflow.com/a/2641293/1066234">la réponse ci-dessus (ECMA-code de style)    .  

0
répondu Kai Noack 2017-09-27 12:22:49

pour 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)  
0
répondu Rodrigo López 2018-08-22 02:09:50

S'il n'y a pas de contrainte de temps, c'est assez simple et simple:

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
-1
répondu Sri 2018-06-28 12:37:45