源码网商城,靠谱的源码在线交易网站 我的订单 购物车 帮助

源码网商城

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)
联系客服
客服电话:
400-000-3129
微信版

扫一扫进微信版
返回顶部