java
Built-in
1 | import java.math.BigInteger; |
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 | public static long gcd(long a, long b) { |
non mod
1 | public static long gcd(long a, long b) { |
bit operation
1 | public static long gcd(long a, long b) { |
references
- Greatest common divisor
- 《编程之美-微软技术面试心得》, 2.7 最大公约数问题
- Greatest common divisor
- Greatest Common Divisor