Greatest common divisor

java

Built-in

1
2
3
4
5
import java.math.BigInteger;

public static long gcd(long a, long b) {
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}

Recursive

To calculate \( gcd(m, n) \), for given values \( 0 \leq m < n\), Euclid’s algorithm uses the recurrence

\(
\begin{align*}
\begin{cases}
gcd(0, n) = n ; \\
gcd(m, n) = gcd(n \hspace{1mm} mod \hspace{1mm} m, m), \hspace{4mm} for \hspace{1mm} m > 0. \\
\end{cases}
\end{align*}
\)

for example, \( gcd(12, 18) = gcd(6, 12) = gcd(0, 6) = 6 \).

1
2
3
4
5
6
7
8
9
public static long gcd(long a, long b) {
if (a == 0)
return b;
if (b == 0)
return a;
if (a > b)
return gcd(b, a % b);
return gcd(a, b % a);
}

non mod

1
2
3
4
5
6
7
8
public static long gcd(long a, long b) {
if (a < b)
return gcd(b, a);
if (b == 0)
return a;
else
return gcd(a - b, b);
}

bit operation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static long gcd(long a, long b) {
if (a < b)
return gcd(b, a);
if (b == 0)
return a;
else {
if ((a & 1) == 0) {
if ((b & 1) == 0)
return (gcd(a >> 1, b >> 1) << 1);
else
return gcd(a >> 1, b);
} else {
if ((b & 1) == 0)
return gcd(a, b >> 1);
else
return gcd(b, a - b);
}
}
}

references