Euclidean Algorithm - Classic Problems | Repovive

CLS8. Euclidean Algorithm

1s256 MB

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both.

Given two integers $a$ and $b$ , compute $\gcd(a, b)$ .

Note: $\gcd(0, n) = \gcd(n, 0) = n$ for any positive $n$ .

$a \quad b$

$\gcd(a, b)$

Input

12 8

Explanation

For this input, the required output is 4.

Output

Input

17 13

Explanation

For this input, the required output is 1.

Output

Input

100 25

Explanation

For this input, the required output is 25.

Output

1s256 MB

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both.

Given two integers $a$ and $b$ , compute $\gcd(a, b)$ .

Note: $\gcd(0, n) = \gcd(n, 0) = n$ for any positive $n$ .

$a \quad b$

$\gcd(a, b)$

Input

12 8

Explanation

For this input, the required output is 4.

Output

Input

17 13

Explanation

For this input, the required output is 1.

Output

Input

100 25

Explanation

For this input, the required output is 25.

Output