Math tip: greatest common divisor

两个求GCD的小程序

Recursive

public int GCD (int a, int b) {
    if (a == 0 || b == 0) return a+b;
    return GCD(b, a % b);
}

Iterative

public int GCD (int a, int b) {
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

Anyway, it is the Euclid’s algorithm: GCD(A, B) = GCD(B, A % B).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s