algorithm

GCD is the greatest common divisor,for example the GCD of 20 and 30 is 10, the GCD of 42 and 63 is 21.

the key to find the GCD can demostrate below:

use the previous example

eg. 42 = 212 and 63 = 213 so 63 - 42 = 21(3-2) = 21, and the 21 is also the GCD of 42 and 21, repeat the process, finally

the both number is the same, and we find the answer


implements with javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function gcd(a, b) {
    if (a > b) {
        c = a - b;
        return gcd(b, c);
    } else if (b > a) {
        c = b - a;
        return gcd(a, c);
    } else {
        return a;
    }
}

res = gcd(30, 20);
console.log(res);

本文作者：oldmee
本文链接：https://oldmee.github.io/2015/05/04/euclid-GCD-algorithm/
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。