详解“辗转相除法”（如何求最大公约数）

本篇博客来讲一讲学习C语言过程中遇到的一种解法——辗转相除法

首先我会介绍辗转相除法的概念，然后会用一道例题进行运用，最后会进行总结

一、辗转相除法的概念

辗转相除法又称欧几里得算法辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。

由概念可知，该算法主要是用于两个非负整数的最大公约数，那么如何求呢，请看下文分析

二、如何利用辗转相除法求两个数的最大公约数

这里先看代码：

int main()
{
    int m = 0;
    int n = 0;
    scanf("%d %d", &m, &n);
    int k = 0;
    while (k = m % n)
    {
        m = n;
        n = k;
    }
    printf("%d\n", n);
 
    return 0;
}

所谓辗转，指的就是把 m % n 赋给k，把 n 赋给 m ，最后再把 k 赋给 n ，直到 k 为零的时候，while循环也会刚好停下，此时的 n 就是 m 和 n 的最大公约数了。

这样说属实有点绕，请C友们结合我画的思路图理解一下：

【笔误