# 淺談輾轉相除法 - Euclidean Algorithm

“In mathematics, the Euclidean algorithm, or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.”

## 簡易實作

• 直覺運算法
• 交換法
• 遞迴法

### 直覺運算法

• 保持用最大數除以較小的數，直到整除為止
int gcd(int a, int b) {
while( a!=0 and b!=0 )
{
if( a >= b ) { a = a%b; }
else if( b > a ) { b = b%a; }
}
return (a >= b) ? a : b;
}

### 交換法

• 讓a保持被除數、b保持除數，相除之後互換
• 當除數為 0，即被除數為最大公因數
int gcd(int a, int b) {
while (b!= 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}

### 遞迴法

• 利用遞迴讓被除數a與除數b互換
if f (int a, int b) {
if (b == 0) return a;
return f(b, a%b);
}

[2] Wiki: 輾轉相除法

[3] Divisor