求兩個整數(a,b)的最大公約數 gcd

// Euclidean Algorithm to find gcd(a, b):
// 1. find gcd(b,r) when  a = b⋅q + r, gcd(a, b) = gcd(b, r)
// 2. substitute a with b, b with r to the recusive step
// 3. if a = 0, gcd(a, b) = b or if b = 0, gcd(a, b) = a
int gcd(int a, int b) {
    int q, r;
    while( a && b){
        q = a / b;
        r = a - q * b;
        a = b;
        b = r;
    }
    if( b==0 ) return a;
    if( a==0 ) return b;
}
#include "stdio.h"
int main(){
    printf("GCD=%d\n", gcd(10, 5));
}