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`

.