> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/algorithmic-pattern/numerical-algorithms/gcd-of-two-numbers.md).

# GCD of two numbers

The Greatest Common Divisor (GCD), or Highest Common Factor (HCF), is the largest number that divides two numbers without a remainder.

## Calculating Greatest Common Divisors <a href="#head-3-8" id="head-3-8"></a>

A naive approach to this is to iterate from all numbers between 1 to $$\text{min}(m,n)$$ and return the biggest number that divides them

```java
int gcd(int m, int n) {
	int maxDivisor = 1;
	for (int i = 1; i < min(m,n); ++i) {
		if(m%i == 0 && n%i ==0) {
			maxDivisor = i;	
		}
	}
	return i;
}
```

{% hint style="info" %}
The GCD is always positive irrespective of the sign of the input numbers. If the given number is negative, we will simply ignore its `-` sign using the `abs()` function
{% endhint %}

To find the GCD of two numbers using recursion, we will be using the principle $$\text{GCD}(a,b) = \text{GCD}(a,b−a)$$

<figure><img src="https://2396813915-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FMQ6PIO0HHybjoa5n1vsw%2Fuploads%2FvORDIZtLY8GkPcM2mN9Q%2FScreenshot%202024-05-03%20at%205.59.35%E2%80%AFPM.png?alt=media&amp;token=593f388c-673e-496e-a4fb-3b78829611be" alt="" width="375"><figcaption></figcaption></figure>

### Steps of the Algorithm

1. Check if `a==0`, if yes, return `b`.
2. Check if `b==0`, if yes, return `a`.
3. Check if `a==b`, if yes, return `a`.
4. Check if `a>b` if yes, call `GCD()` function using the arguments `a−b` and `b` recursively, otherwise call `GCD()` function using the arguments `a` and

#### Implementation

```java
int gcd(int a , int b) {
  if(a == 0) return b;
  if(b == 0) return a;
  return  a > b ? gcd(a-b,b) : gcd(a,b-a);
}
```

### **Complexity Analysis**

#### Time Complexity

$$\text{O}(\text{max}(a,b))$$ In this algorithm, the number of steps are linear, for e.g. $$GCD(x,1)$$ in which we will subtract $$1$$ from $$x$$ in each recursion, so the time complexity will be  $$\text{O}(\text{max}(a,b))$$

#### Space Complexity

The space complexity here is $$\text{O}(\text{max}(a,b))$$ because the space complexity in a recursive function is equal to the maximum depth of the call stack.

***