当前位置：首页 > 资讯 > 技术文档

C语言辗转相除法求2个数的最小公约数

时间：2020-09-16 14:27 编辑：来源：阅读：
扫一扫，手机访问

摘要：C语言辗转相除法求2个数的最小公约数

辗转相除法最大的用途就是用来求两个数的最大公约数。用（a,b）来表示a和b的最大公约数。有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。（证明过程请参考其它资料）例：求 15750 与27216的最大公约数。解： ∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466） ∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284) ∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898） ∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386） ∵2898=1386×2+126 ∴（2898，1386）=（1386，126） ∵1386=126×11 ∴（1386，126）=126 所以（15750，27216）=126 辗转相除法比较适合用来求两个比较大的数的最大公约数。代码如下：

#include<stdio.h>
int main()
{
  int a,b,temp,x;
  scanf("%d%d",&a,&b);
  if(a>b)
  {
    temp=b;
    b=a;
    a=temp;
  }
  while(b%a!=0)
  {
    x=b%a;
    b=a;
    a=x;
  }
  printf("%d",a);
}

以上所述是小编给大家介绍的C语言辗转相除法求2个数的最小公约数，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对编程素材网网站的支持！

全部评论(0)

上一篇：C++实现闹钟程序的方法
下一篇：C++设计模式之工厂方法模式

资讯排行榜
更多>>