JS jak znaleźć największego wspólnego dzielnika

Question

Chciałbym znaleźć największy wspólny dzielnik za pomocą JavaScript.

Ktoś zrobił to wcześniej i chciał się podzielić?

Answer 1

Oto rozwiązanie rekursywne.

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

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

Nasza baza jest przypadek, gdy b jest równa 0. W takim przypadku zwracamy a.

Kiedy mamy recursing, zamieniamy argumenty wejściowe, ale przekazujemy pozostałą część a/b jako drugi argument.

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

Zaczerpnięte z Wikipedii.

rekurencyjne:

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

Iterative:

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

• edytowane na komentarz użytkownika