Le plus petit commun multiple pour 3 nombres ou plus

Question

Comment calculer le plus petit commun multiple de plusieurs nombres ?

Jusqu'à présent, je n'ai été capable de le calculer qu'entre deux nombres. Mais je n'ai aucune idée de comment l'étendre pour calculer 3 nombres ou plus.

Voici comment j'ai procédé jusqu'à présent

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

Avec gcd est la fonction qui permet de calculer le plus grand diviseur commun pour les nombres. Utilisation de l'algorithme euclidien

Mais je n'arrive pas à trouver comment le calculer pour 3 nombres ou plus.

Answer 1

Vous pouvez calculer la LCM de plus de deux nombres en calculant itérativement la LCM de deux nombres, soit

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

Answer 2

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 comme suit que :

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

Answer 3

Voici une mise en œuvre de type ECMA :

function gcd(a, b){
    // Euclidean algorithm
    while (b != 0){
        var temp = b;
        b = a % b;
        a = temp;
    }
    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 4

Je viens de comprendre ça 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

J'ai même pris le temps d'écrire mon propre gcd pour la trouver dans Prelude ! Beaucoup d'apprentissage pour moi aujourd'hui :D

Answer 5

Un peu de code Python qui ne nécessite pas de fonction pour le pgcd :

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 cela ressemble dans le terminal :

$ python lcm.py 10 15 17
510