It is better to implement the binary version of the Euclid algorithm. It has a smaller constant hidden in the O(log(n)) entry, since dividing by 2 is much faster than taking the remainder on modern processors.

A little longer, but a little faster, since without recursion.

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

I always write like this:

int gcd(const int &a, const int &b){return a ? gcd(b%a, a) : b;}

Experiment

It became interesting whether division is really so bad and how much it affects performance. I made a small "benchmark":

#include <stdio.h>
#include <sys/time.h>

/**
 * Different implementations of GCD algorithm
 */
int gcd(const int a, const int b) { return a ? gcd(b%a, a) : b; }

int iterable_gcd(int a, int b) { 
    int t;
    while (a) t = a, a = b % a, b = t;
    return b; 
}

int cycled_gcd(int a, int b) {
    for (;;) {
        a %= b;
        if (!a) return b;
        b %= a;
        if (!b) return a;
    }
}

int binary_gcd(int u, int v) {
    int shift, t;
    if (u == 0) return v;
    if (v == 0) return u;
    for (shift = 0; ((u | v) & 1) == 0; ++shift) {
        u >>= 1;
        v >>= 1;
    }
    while ((u & 1) == 0) u >>= 1;
    do 
    {
        while ((v & 1) == 0) v >>= 1;
        if (u > v) t = v, v = u, u = t;
        v = v - u;
    } 
    while (v != 0);
    return u << shift;
}

/**
 * Timers
 */
void timeit(int (*implementation)(int, int), const int from, const int to) {
    int i, j;
    struct timeval tv1, tv2;
    gettimeofday(&tv1, NULL);
    for (i = from; i < to; ++i) {
        for (j = from; j < to; ++j) {
            implementation(i, j);
        }
    }
    gettimeofday(&tv2, NULL);
    printf("Total time = %f seconds\n",
        (double) (tv2.tv_usec - tv1.tv_usec) / 1000000 +
        (double) (tv2.tv_sec - tv1.tv_sec)
    );
}

void timeit_small_numbers(int (*implementation)(int, int)) {
    const int from = 1000, to = from + 9*1000;
    timeit(implementation, from, to);
}

void timeit_big_numbers(int (*implementation)(int, int)) {
    const int from = 1000*1000*1000, to = from + 9*1000;
    timeit(implementation, from, to);
}

int main(int argc, char *argv[]) {
    int (*implementations[])(int,int) = {
        cycled_gcd, 
        gcd, 
        iterable_gcd, 
        binary_gcd
    };
    const int size = sizeof(implementations) / sizeof(implementations[0]);
    for (int i = 0; i < size; ++i) timeit_small_numbers(implementations[i]);
    for (int i = 0; i < size; ++i) timeit_big_numbers(implementations[i]);
    return 0;
}

• gcd - easy to remember relazation is not difficult to implement.
• cycled_gcd - was suggested in one of the answers, but it is sometimes even worse for gcd.
• iterable_gcd - recursion can impose its own time costs, so added an iterative an option, but if the flag -O3 does its job, then these costs are very small
• binary_gcd - based on wiki code

If we take numbers from 1000 to 10*1000 and from billion to billion + 9*1000, we will have different results.

$ gcc -O3 run.c -o run
$ ./run
Test on small numbers
Total time = 8.311910 seconds
Total time = 8.329916 seconds
Total time = 8.333715 seconds
Total time = 7.837158 seconds
Test on big numbers
Total time = 10.425167 seconds
Total time = 10.481676 seconds
Total time = 10.460748 seconds
Total time = 17.428999 seconds

On small numbers binary_gcd almost 7% faster than any of the implementations. This is a very good result. Unless, of course, you are sure that you will not have large numbers. Why?

Because on large numbers binary_gcd it degrades quickly and already shows a 67% longer running time than the other implementations.

Output

Division-based implementations do not degrade as quickly, although they are inferior in performance on small numbers.