欧几里德算法也就是辗转相除法,有着2000年的历史了。欧几里德算法依据的算法理论是一个定理:gcd(a,b) = gcd(b,a mod b)。
实现源码为:
//递归实现 int gcd(int m, int n) { if (m < n) { int tem = m; m = n; n = tem; } if (n == 0) return m; else return gcd(m, m%n); }
//非递归实现 int gcd(int m, int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (n == 0) return m; while (n > 0) { int tmp = m % n; m = n; n = tmp; } return m; }