辗转相除法, 又名欧几里得算法(Euclidean algorithm),目的是求出两个正整数的最大公约数。 它是已知最古老的算法, 其可追溯至公元前300年前。 这条算法基于一个定理: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。 比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。
它的具体做法是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。这个和更相减损术有着异曲同工之处。
接下来是 --> C语言程序中运用辗转相除法去求两个数的最大公约数的代码:
//两个数最大公约数 int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); //求a和b的较小值 int min = a < b ? a : b; int m = 0; //for (m = min; m > 0; m++) //另一种方法 //{ // if (a % m == 0 && b % m == 0) // { // break; // } //} //辗转相除法 --> 效率更高 while (a % b) { int c = a % b; a = b; b = c; } printf("%d", b); return 0; }
希望这篇文章能够对大家有所帮助
最后 ---> 觉得好的话请点个赞呗