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个数的最小公约数,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对<计算机技术网>网站的支持!

—-想了解C语言辗转相除法求2个数的最小公约数分享!全部内容且更多的C语言教程关注<计算机技术网>

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/481922.html

(0)
上一篇 2020年11月9日
下一篇 2020年11月9日

精彩推荐