Table of Contents

• 1 GCD 算法的基本原理
• 2 GCD 算法的实现
  • 2.1 递归实现
  • 2.2 迭代实现

1 GCD 算法的基本原理

GCD=Greatest Common Divisor

欧几里德定理

若 a=b×r+q 则gcd(a, b) = gcd(b, q).

欧几里德定理的证明

a = b × r + q

设c = gcd(a, b), a = m×c, b= n×c

q = a - b× r = (m - n × r)×c

下面证明 m-n×r与n互质：

假设不互质，则存在k使得 m-n×r = x×k, n = y×k.

则:

a = m×c = (n×r + x×k)×c = (y×r + x×k)×c×k

b = n×c = y×c×k

与 c=gcd(a, b) 矛盾。

辗转相除法的算法实现

a = b × r_1 + q_1if q_1 = 0      then return belseb = q_1 × r_2 + q_2if q_2 = 0      then return q_1else

……

直到找到GCD为止。

2 GCD 算法的实现

2.1 递归实现

int gcd(int a, int b){        if(!b) return a;        else  return gcd(b, a%b );}

2.2 迭代实现

int gcd(int a, int b){        int c = a%b;        while(c){                a = b;                b = c;                c = a % b;        }        return b;}

Author: visaya fan 

Date: 2011-08-11 18:01:00

HTML generated by org-mode 6.33x in emacs 23