JS come trovare il massimo comune divisore

Question

Mi piacerebbe trovare il massimo comun divisore usando JavaScript.

Chiunque l'ha già fatto e ha voluto condividere?

Answer 1

Ecco una soluzione ricorsiva.

var gcd = function(a, b) { 
    if (! b) { 
     return a; 
    } 

    return gcd(b, a % b); 
}; 

Il nostro scenario di base è quando b è uguale a 0. In questo caso, restituiamo a.

In fase di ricorsività, scambiamo gli argomenti di input ma passiamo il resto di a/b come secondo argomento.

Answer 2

function egcd(a, b) { 
    if (a == 0) 
     return b; 

    while (b != 0) { 
     if (a > b) 
      a = a - b; 
     else 
      b = b - a; 
    } 

    return a; 
} 

Answer 3

Tratto da Wikipedia.

ricorsivo:

function gcd_rec(a, b) { 
    if (b) { 
     return gcd_rec(b, a % b); 
    } else { 
     return Math.abs(a); 
    } 
} 

iterativo:

function gcd(a,b) { 
    a = Math.abs(a); 
    b = Math.abs(b); 
    if (b > a) {var temp = a; a = b; b = temp;} 
    while (true) { 
     if (b == 0) return a; 
     a %= b; 
     if (a == 0) return b; 
     b %= a; 
    } 
} 

• edito per commentare dell'utente