### Greatest Common Divisor (GCD) – Finding the highest common factor of two numbers

When given two integers, it is often required to find their greatest common divisor (GCD), i.e., the largest positive integer that divides both numbers without leaving any remainder. There exist popular algorithms to compute GCD of two positive integers, such as the Euclidean algorithm and its modern versions, binary GCD, and the extended Euclidean algorithm.

### Simple approach for finding GCD

The simple approach to calculate GCD involves finding all divisors of both numbers, then comparing them to find the highest common divisor. This approach is of complexity O(n), where n is the smaller of the two numbers.

#### C++ Implementation

int gcd(int a, int b) {

int gcd = 1;

for(int i = 1; i <= a && i <= b; i++) {
if(a % i == 0 && b % i == 0)
gcd = i;
}
return gcd;
}

#### Python Implementation

def gcd(a, b):

gcd = 1

for i in range(1, min(a, b) + 1):

if a % i == b % i == 0:

gcd = i

return gcd

#### Java Implementation

public static int gcd(int a, int b) {

int gcd = 1;

for(int i = 1; i <= a && i <= b; i++) {
if(a % i == 0 && b % i == 0)
gcd = i;
}
return gcd;
}

### Efficient Approach: Euclid’s Algorithm

The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers. The algorithm is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.

#### C/C++ Implementation of Efficient Approach

int gcd(int a, int b) {

if (b == 0)

return a;

return gcd(b, a % b);

}

#### Java Implementation of Efficient Approach

public static int gcd(int a, int b) {

if (b == 0)

return a;

return gcd(b, a % b);

}

#### Python Implementation of Efficient Approach

def gcd(a, b):

if b == 0:

return a

return gcd(b, a % b)

### Practice Questions

Q1: How do you find the GCD of two numbers?

Ans: GCD of two numbers can be found using the Euclidean algorithm. Initially, take two numbers as input. Then repeat the following steps until the second number becomes 0: (a) Divide the first number by the second number. (b) Set the first number as the second number and the remainder as the second number. (c) The GCD is the last non-zero remainder.

Q2: Can we find the GCD of negative numbers?

Ans: Yes, the GCD algorithm is independent of the sign of numbers, so the GCD can be found irrespective of the signs of the numbers.

Q3: Do any two positive integers always have a GCD?

Ans: Yes, every pair of positive integers has a GCD. It can be 1 if the numbers are co-prime.

### Finding GCD of Two Non-Negative Integers

The following code finds the greatest common divisor (GCD) of two non-negative integers using the Euclidean algorithm:

```python

def gcd(a, b):

if b == 0:

return a

else:

return gcd(b, a % b)

a = 32

b = 20

print("GCD of", a, "and", b, "is", gcd(a, b))

a = 98

b = 70

print("GCD of", a, "and", b, "is", gcd(a, b))

a = 399

b = 437

print("GCD of", a, "and", b, "is", gcd(a, b))

```

**Output:**

```

GCD of 32 and 20 is 4

GCD of 98 and 70 is 14

GCD of 399 and 437 is 19

```

The function `gcd()` takes two arguments `a` and `b`, and returns their GCD using the Euclidean algorithm. It repeatedly subtracts the smaller number from the larger number until both numbers become equal, which is the GCD. The values `a`, `b` and `gcd(a,b)` are printed for the given input values.

### Finding the GCD using a Simple Approach

function findGCD(a, b) {

// Determine the smaller number

const smaller = Math.min(a, b);

```
```

` // Iterate through all numbers from smaller to 1`

for (let i = smaller; i >= 1; i--) {

// If both a and b are divisible by i, return i as the GCD

if (a % i === 0 && b % i === 0) {

return i;

}

}

}

This code uses a simple approach to find the Greatest Common Divisor (GCD) of two numbers a and b. It iterates through all numbers from the smaller of the two inputs down to 1, checking if each number is a common divisor of a and b. The first number found to be a common divisor is returned as the GCD.

### Implementation of GCD algorithm in C++

int find_gcd(int num1, int num2) {

int min_num = std::min(num1, num2); //find the minimum number from num1 and num2

int gcd;

for (int i = min_num; i > 0; --i) {

if (num1 % i == 0 && num2 % i == 0) { //check if i is the GCD of num1 and num2

gcd = i;

return gcd; //return i as GCD

}

}

}

The above code implements the Euclidean algorithm to find the greatest common divisor (GCD) between two integers. The function takes in two integers and returns their GCD. The implementation first finds the minimum number between the two integers. Then, it iterates from the minimum number to 1 to find the highest number that divides both integers without leaving a remainder. This number is the GCD and thus, it is returned by the function.

### Greatest Common Divisor function using loop

This function takes in 2 integers (a,b) and returns their greatest common divisor using a loop

def find_gcd(a, b): #function name and variables updated

if a > b:

smaller_number = b #variable name updated

else:

smaller_number = a

gcd = 1 #gcd initialized

for i in range(1, smaller_number + 1):

if ((a % i == 0) and (b % i == 0)):

gcd = i

return gcd

This updated function has more descriptive variable and function names, and comments have been added to the code for better understanding.

### Finding the GCD of Two Numbers in Java

public class Main {

public static void main(String[] args) {

// Find the GCD of two numbers

int num1 = 81, num2 = 153;

int greatestCommonDivisor = 1;

```
```

` // Loop from 1 to the smaller of the two numbers`

for (int i = 1; i <= Math.min(num1, num2); i++) {
if (num1 % i == 0 && num2 % i == 0) {
greatestCommonDivisor = i;
}
}
System.out.println("GCD of " + num1 + " and " + num2 + " is: " + greatestCommonDivisor);
}
}

This code finds the Greatest Common Divisor (GCD) of two numbers by looping through all possible numbers between 1 and the smaller of the two numbers, and checking whether each number is a divisor of both. If a number is a divisor of both, it is considered a candidate for the GCD, and if it is larger than the previous candidate, it replaces it as the new GCD.

H3 tag: Efficient Approach: Euclid's Algorithm

The Euclid's Algorithm is an efficient algorithm for finding the Greatest Common Divisor (GCD) of two numbers. This algorithm is based on two facts:

1. If we subtract smaller from larger, GCD does not change.

2. We can stop the algorithm when we find remainder 0 after dividing small by large.

Code:

```

def euclidean_algorithm(a, b):

# ensure a is greater than b

if a < b:
a, b = b, a
# loop until remainder is 0
while b != 0:
temp = a % b
a = b
b = temp
return a
```
In the code above, `euclidean_algorithm` function implements the Euclid's Algorithm. The function takes two inputs `a` and `b` and returns the GCD of these two numbers.

### C++ Function to Calculate GCD of Two Numbers

int GCD(int num1, int num2) {

if (num1 == 0) {

return num2;

}

return GCD(num2 % num1, num1);

}

This implementation uses recursion to efficiently calculate the greatest common divisor of two given numbers, `num1`

and `num2`

. It first checks if `num1`

is 0, and if so, returns `num2`

, since the GCD of any number and 0 is the number itself. Otherwise, it uses the modulo operator to calculate the remainder when `num2`

is divided by `num1`

, and then recursively calls itself with the arguments `num1`

as the new remainder and `num2`

as the original value of `num1`

. This continues until the value of `num1`

is 0, at which point the function is terminated and the current value of `num2`

is returned as the GCD.

### Java Implementation of Extended Euclidean Algorithm

import java.util.*;

import java.lang.*;

```
```

`class ExtendedEuclideanAlgorithm {`

public static int findGCD(int firstNum, int secondNum) {

if (firstNum == 0)

return secondNum;

return findGCD(secondNum % firstNum, firstNum);

}

}

This is a Java program to find the greatest common divisor (GCD) of two numbers using the Extended Euclidean Algorithm. The code is optimized and has been updated with proper variable and class names.

### Python Function to Find GCD of Two Numbers

Here's an efficient implementation in Python to find the GCD of two numbers using the Euclidean algorithm:

def find_gcd(num1, num2):

if num1 == 0:

return num2

return find_gcd(num2 % num1, num1)

The time complexity of this function is O(log min(num1, num2)) and the space complexity is O(1).

### Practice Questions

Here are some practice questions:

// Find the greatest common divisor

// Input: two integers a and b

// Output: greatest common divisor of a and b

int gcd(int a, int b) {

if(b == 0) {

return a;

}

return gcd(b, a%b);

}

```
``` // Find the largest coprime divisor

// Input: two integers a and b

// Output: largest coprime divisor of a and b

int lcp(int a, int b) {

while(gcd(a, b) != 1) {

a /= gcd(a, b);

}

return a;

}

` // Find GCD of an array of integers`

// Input: array of n integers

// Output: greatest common divisor of the array of integers

int gcd(int arr[], int n) {

int result = arr[0];

for(int i = 1; i < n; i++) {
result = gcd(arr[i], result);
if(result == 1) {
return 1;
}
}
return result;
}

### Frequently Asked Questions

### Finding the GCD of Two Numbers using the Euclidean Algorithm

To find the GCD of two numbers, we can use the Euclidean algorithm, which has a time complexity of log(min(a,b)).

function gcd(a, b) {

if(b === 0) {

return a;

} else {

return gcd(b, a % b);

}

}

In the above code, we define a function gcd(a, b) that takes two numbers as input and recursively calls itself with (b, a % b) until b becomes 0, at which point the function returns a as the GCD.

### Finding GCD of Negative Numbers

Yes, it is possible to find the GCD of negative numbers. For example, GCD(6,-12) can also be represented as GCD(-6,12) or GCD(-6,-12) or GCD(6,12) and the result will be 6.

from math import gcd

```
```a = 6

b = -12

`result = gcd(a,b)`

print(result)

### Do two positive integers always have a greatest common divisor (GCD)?

Yes, every pair of positive integers has a GCD. The GCD is always the largest positive integer that divides both numbers without leaving a remainder.