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.
