Kensuke Kousaka's Blog

Notes for Developing Software, Service.

How to implement Euclidean algorithm to find GCD

This article describes how to implement Euclidean algorithm, which can find greatest common divisor of two numbers, in C and Java.

Following code is implementation sample in C.

#include <stdio.h>

int getGCD(int x, int y) {
    int tmp = 0;

    // if y is greater than x, then swap them using tmp
    if (x < y) {
        tmp = x;
        x = y;
        y = tmp;
    }

    // return -1 when y is less than or equal to 0
    if (y <= 0) {
        return -1;
    }

    if (x % y == 0) {
        return y;
    }

    return getGCD(y, x % y);
}

int main() {
    int x, y, n;
    int aspX, aspY;

    x = 1920;
    y = 1080;

    if ((n = getGCD(x, y)) > 0) {
        printf("GCD between x and y is %d\n", n);

        aspX = x / n;
        aspY = y / n;

        printf("print aspect ratio\n");
        printf("%d : %d\n", aspX, aspY);
    }
}

Following code is Euclidean algorithm implementation sample in Java.

public class GetGCD {
    public static int getGCD(int x, int y) {
        int tmp = 0;

        // if y is greater than x, then swap them using tmp
        if (x < y) {
            tmp = x;
            x = y;
            y = tmp;
        }

        // return -1 when y is less than or equal to 0
        if (y <= 0) {
            return -1;
        }

        if (x % y == 0) {
            return y;
        }

        return getGCD(y, x % y);
    }
}

The following is Java code sample to use GetGCD.

int gcd = GetGCD.getGCD(1920, 1080);

Variable gcd contains GCD between GetGCD.getGCD's parameters, or -1 when couldn't find GCD.

String aspect = String.valueOf(1920 / gcd) + " : " + String.valueOf(1080 / gcd);

Result of variable aspect is 16 : 9.