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

2018-06-18 04:11:01来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

辗转相除法最大的用途就是用来求两个数的最大公约数。 

用(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);
}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C语言计算字符串子串出现的次数

下一篇:[APUE]文件和目录(中)