欧几里得算法-求最大公因数

欧几里得算法(Euclidean algorithm)

欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公因数。
github源码

最大公因数(Greast Common Divisor)

定义： 对于整数a,b,其最大公因数是能同时整除a和b的最大整数，用gcd(a,b)来表示。

由于最大公因数必须是正数，所以有gcd(a,b) = gcd(a,-b) = gcd(-a,b) = gcd(-a,-b)。

互素：整数a,b互素，当且仅当它们只有一个正整数公因子1，即gcd(a,b) = 1

推理：

设:
$a \ge b \gt 0$
$a = q_{1}b + r_{1} ,(0 \le r_{1} \lt b)$
$d = gcd(a, b)$

则:
情形1： $r_{1} = 0$
则b整除a，即$d = gcd(a, b) = b$

情形2： $r_{1} \neq 0$
则d一定能够整除$r_{1}$，证明：
$d = gcd(a,b)$
则
a mod d = 0 -> $a = k_{1}d$
b mod d = 0 -> $b = k_{2}d$
$r_{1} = a - q_{1}b = k_{1}d - q_{1}k_{2}d = d(k_{1} - q_{1}k_{2})$
即
$r_{1}$ mod d = 0

对任意一个b和$r_{1}$的公因数c，有：
b mod c = 0 -> $b = k_{3}c$
$r_{1}$ mod c = 0 -> $r_{1} = k_{4}c$
则 $a = q_{1}b + r_{1} = q_{1}k_{3}c + k_{4}c = c(q_{1}k_{3} + k_{4})$,即
a mod c = 0
则 c 是整数a,b的公因数，$c \le d$,
那么 $d = gcd(b,r_{1})$
即将求整数a,b的最大公因数转换为了求b,$r_{1}$的最大公因数。

求$gcd(b,r_{1})$同样可设$b = q_{2}r_{1} + r_{2} ,(0 \le r_{2} \lt r1)$
若$r_{2} = 0$, 则$d = r_{1}$, 若$r_{2} \neq 0$，则 $d = gcd(r_{1},r_{2})$。

依此循环，余数会一直递减，当余数为0时，循环停止，求得d。

展开如下:
$a = q_{1}b + r_{1} ,(0< r_{1} < b)$
$b = q_{2}r_{1} + r_{2} ,(0< r_{2} < r_{1})$
$r_{1} = q_{3}r_{2} + r_{3} ,(0< r_{3} < r_{2})$
…

$r_{n-2} = q_{n}r_{n-1} + r_{n} ,(0< r_{n} < r_{n-1})$
$r_{n-1} = q_{n+1}r_{n} + 0$
$d = gcd(a,b) = r_{n}$

该算法称为欧几里得算法。

递归代码

Euclid(a, b){
	if(b == 0){
		return a;
	}else{
		return Euclid(b, a%b);
	}
}

C实现

递归方式实现

int gcd1(int a, int b){
    int a_temp;
    int b_temp;
    int r;
    if(a < 0){
        a_temp = -a;
    }else{
        a_temp = a;
    }
    if(b < 0){
        b_temp = -b;
    }else{
        b_temp = b;
    }
    if(b_temp > a_temp){
        r = a_temp;
        a_temp = b_temp;
        b_temp = r;
    }
    if(b_temp == 0){
        return a_temp;
    }else{
        return gcd1(b_temp,a_temp % b_temp);
    }
}

循环方式实现

int gcd2(int a, int b){
    int a_temp;
    int b_temp;
    int r;
    if(a < 0){
        a_temp = -a;
    }else{
        a_temp = a;
    }
    if(b < 0){
        b_temp = -b;
    }else{
        b_temp = b;
    }
    if(b_temp > a_temp){
        r = a_temp;
        a_temp = b_temp;
        b_temp = r;
    }
    if(b_temp == 0) return a_temp;
    r = a_temp % b_temp;
    while(r != 0){
        a_temp = b_temp;
        b_temp = r;
        r = a_temp % b_temp;
    }
    return b_temp;
}