gcd.c

// gcd a b | a`mod`b == 0 = b
//         | otherwise = gcd b (a`mod`b)

#define GCD(a,b) (GCD1((a),(b)))
#define GCD1(a,b) a%b==0?b:GCD2(b,(a%b))
#define GCD2(a,b) a%b==0?b:GCD3(b,(a%b))
#define GCD3(a,b) a%b==0?b:GCD4(b,(a%b))
#define GCD4(a,b) a%b==0?b:GCD5(b,(a%b))
#define GCD5(a,b) a%b==0?b:GCD6(b,(a%b))
#define GCD6(a,b) a%b==0?b:GCD7(b,(a%b))
#define GCD7(a,b) a%b==0?b:GCD8(b,(a%b))
#define GCD8(a,b) a%b==0?b:GCD9(b,(a%b))
#define GCD9(a,b) a%b==0?b:GCD10(b,(a%b))
#define GCD10(a,b) a%b==0?b:GCD11(b,(a%b))
#define GCD11(a,b) a%b==0?b:GCD12(b,(a%b))
#define GCD12(a,b) a%b==0?b:GCD13(b,(a%b))
#define GCD13(a,b) 1

// a*b/c
#define MULDIV(a,b,c) (a*(b/GCD(b,c))/(c/GCD(b,c)))


#include <stdio.h>

int gcd(int a,int b) {
    for(;;) {
        a %= b;
        if (a==0) return b;
        b %= a;
        if (b==0) return a;
    }
}

int main(void) {
    printf("%d\n",GCD(10,15));
    printf("%d\n",GCD(89,144));
    printf("%d\n",GCD(80,130));
    printf("%d\n",GCD(130,210));
    printf("%d\n",GCD(210,340));
    printf("%d\n",GCD(340,550));
    printf("%d\n",GCD(550,890));
    printf("%d\n",GCD(890,1440));
    //1,1,2,3,5,8,13,21,34,55,89,144
    for (int i=1;i<1000;++i) {
        for (int j=1;j<1000;++j) {
            if(GCD(i,j) != gcd(i,j)) {
                printf("wrong for (%d,%d)\n",i,j);
            }
        }
    }
    printf("%d <-> %d\n",123456*7890123/7890123,MULDIV(123456,7890123,7890123));
    return 0;
}