欧几里得算法求解GCD

GCD(最大公约数)

欧几里得算法(辗转相除法)

原理

if(a%b==0)
    GCD=b 
else
    GCD=b%(a%b)

1. 基本情况： 如果其中一个数为0，则另一个非零数一定就是两数的 G C D GCD GCD(任何非零数与0的GCD都是该非零数本身)。

2. 归纳假设： 假设我们已经证明了对于所有符合条件的 ( a , b ) (a, b) (a,b)，辗转相除法能够正确地给出 g c d ( a , b ) gcd(a, b) gcd(a,b)。

3. 归纳步骤： 现在考虑一个新的(a, b)对，其中a和b都不为0。根据辗转相除法的步骤，我们执行以下操作：

   a. 用b去除a，得到余数r。根据欧几里德算法的定义， g c d ( a , b ) = = g c d ( b , r ) gcd(a, b) == gcd(b, r) gcd(a,b)==gcd(b,r)。

   b. ∵ \because ∵ r==a%b，根据整除的性质， ∃ \exist ∃整数 q q q，使得 a = b q + r a = bq + r a=bq+r。

   c. ∵ \because ∵ g c d ( a , b ) = = g c d ( b , r ) gcd(a, b) == gcd(b, r) gcd(a,b)==gcd(b,r)，且r==a%b，所以我们可以将问题转化为 g c d ( b , r ) gcd(b, r) gcd(b,r)。

   d. 接着，令 b = r ， r = b b=r，r=b b=r，r=b，然后重复步骤a。

   e. 这个过程会一直持续下去，直到 r = = 0 r==0 r==0。这时，b即为 g c d ( a , b ) gcd(a,b) gcd(a,b)。

实现

extern int m,n;//已在其他位置定义m:被除数 n:除数

非递归算法

int gcd(int m,int n){
    int r;//暂存余数
    do{
        r=m%n;
        if(r!=0){
            m=n,n=r;
    	}
	}while(r!=0);
	return n;
}

递归算法

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