辗转相除法求最大公约

辗转相除法，又称欧几里德算法，是一种用于求两个数的最大公约数的方法。这个方法的基本原理是将较大的数除以较小的数，然后用除数和余数反复做除法运算，直到余数为0。此时，最后一个除数就是这两个数的最大公约数。

具体来说，使用辗转相除法求最大公约数的表达式为：gcd(a, b) = gcd(b, a % b)，其中gcd是最大公约数的缩写，a和b是要求最大公约数的两个数，%表示取余操作。

辗转相除法的实现可以使用循环结构来完成。例如，在C语言中，可以使用下面的代码来实现辗转相除法求最大公约数：

#include <stdio.h>

int main() {
  int m = 0;
  int n = 0;
  scanf("%d %d", &m, &n);

  int r = 0;
  while (r = m % n) {
    m = n;  // 以除数作为被除数
    n = r;  // 以余数作为除数
  }

  printf("%d\n", n);  // 最后的除数为最大公约数

  return 0;
}

以上代码可以通过输入两个数m和n来求它们的最大公约数，并输出结果。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [【算法】辗转相除法求最大公约数](https://blog.csdn.net/Qiuhan_909/article/details/125941749)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [辗转相除法 (欧几里得算法) 求最大公约数](https://blog.csdn.net/MHX_Star/article/details/121898894)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]