# 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`.