GCD

The greatest common divisor (GCD) of two numbers is the largest number that divides both numbers. Several algorithms can efficiently compute the GCD.

Java example (Euclidean algorithm):

1
2
3
4
5
6

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int d = gcd(48, 18); // Returns 6

C++ example (Euclidean algorithm):

1
2
3
4
5
6

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);  
}

int d = gcd(48, 18); // Returns 6

Python example (Euclidean algorithm):

1
2
3
4
5
6

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)

d = gcd(48, 18) # Returns 6

The GCD can be computed efficiently in O(log(min(a,b))) time via the Euclidean algorithm, which recursively computes the GCD of remainders.

Other methods include binary GCD and using prime factorization. GCD is useful for simplifying fractions and various mathematical operations.

The Greatest Common Divisor (GCD) is the largest positive integer that divides two or more integers without leaving a remainder. For example, the GCD of 8 and 12 is 4. The GCD of two numbers a and b can be found using Euclid’s algorithm. The algorithm is based on the principle that the GCD of a and b is the same as the GCD of a and a % b.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class GCD {
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(gcd(8, 12));  // Output will be 4
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    cout << gcd(8, 12) << endl;  // Output will be 4
    return 0;
}

Python

1
2
3
4
5
6

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(8, 12))  # Output will be 4

In these examples, the function gcd takes two integers a and b as input. It uses recursion and Euclid’s algorithm to find the GCD. If b is 0, it returns a. Otherwise, it calls itself with b and a % b.