首页 > itarticle > 最大公因子

最大公因子

admin 11月 14, 2020 0

求两个数的最大公因子，使用“辗转相除法”。

原理

若r=a%b，则gcd(a,b)=gcd(b,r)。

推导

因为r=a%b，所以a=bq+r，r=a-bq。
a=bq+r，能被b,r整除的，则一定能被a整除，自然也能被a,b整除
r=a-bq，能被a,b整除的，则一定可以被r整除，自然也能被b,r整除
显然gcd(a,b)=gcd(b,r)。

代码

代码很简单：

int (int a,int b)  
{  
    int m=a,n=b;  
    if (a < b)  
    {  
        m=b;  
        n=a;  
    }   
    if(m%n==0)  
        return b;  
    else 
        return gcd(n,r);  
}