编程爱好者
 ppppp.cn
C语言求最大公约数
(发布日期: 2022-03-19  阅读:280次)

C语言求最大公约数

这是一个C语言 while 循环示例:求正整数 m 和 n 的最大公约数。


问题分析

输入:两个正整数。
输出:一个正整数(最大公约数)。
最大公约数(gcd)是指几个数共有的因数之中最大的一个数,比如 8 和 12 的最大公约数是 4,一般记作 gcd(8,12)=4。
求两个正整数的最大公约数可以使用辗转相除法。辗转相除法是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》中提出的,利用这个方法可以较快地求出两个自然数的最大公约数。
辗转相除法求两个正整数的最大公约数的具体步骤:用较大的数除以较小的数,如果余数不为 0,则将余数和较小的数(除数)构成一对新数,继续用其中较大的数除以较小的数,这样反复进行上面的除法,直到大数被小数除尽(余数为 0),这时较小的数就是原来两个数的最大公约数(见图 1)。
辗转相除法求两个正整数的最大公约数
图 1:辗转相除法求两个正整数的最大公约数

算法描述

N-S 图
 
代码清单 2:求正整数 m 和 n 的最大公约数
		
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main( )
  4. {
  5. int m,n,r;
  6. printf("输入两个正整数(空格分隔):\n");
  7. scanf("%d %d",&m,&n);
  8. r = m % n; //r取m除以n的余数
  9. while(r != 0) //辗转相除
  10. {
  11. m = n; //小数给m
  12. n = r; //余数给n
  13. r = m % n; //r再次取m除以n的余数
  14. }
  15. printf("最大公约数是%d\n",n);
  16. system("pause");
  17. return 0;
  18. }

运行结果:

输入两个正整数(空格分隔):
56 72
最大公约数是8

知识点总结

辗转相除法求最大公约数:始终用较大的数除以较小的数,直至除尽。


ref:  https://www.weixueyuan.net/a/326.html