In this C programming tutorial, we will learn multiple approaches to finding the GCD for two numbers. But before learning those approaches let us understand what is GCD?
What is GCD (Greatest Common Divisor)?
The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the given integers without leaving a remainder. It is also known as the Greatest Common Factor (GCF) or Highest Common Divisor (HCD).
Example:
Let's find the GCD of two numbers, 36 and 48. The divisors of 36 are: 1, 2, 3, 4, 6, 9, 12, 18, 36. The divisors of 48 are: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. The common divisors of 36 and 48 are: 1, 2, 3, 4, 6, 12. Among the common divisors, the greatest one is 12.
Therefore, GCD(36, 48) = 12.
There are multiple approaches to finding GCD in C programming and here we are going to learn below three approaches:
Approach 1: Euclidean Algorithm.
This is the most commonly used method for finding the GCD of two numbers. It involves successive division of the larger number by the smaller number until the remainder becomes zero.
Here is an example of how the Euclidean Algorithm work:
Example: Find the GCD of 36 and 48.
Step 1: Divide the larger number by the smaller number and find the remainder.
48 ÷ 36 = 1 remainder 12
Step 2: Now, replace the larger number with the smaller number, and the smaller number with the remainder from Step 1.
New larger number = 36 New smaller number = 12
Step 3: Repeat the process until the remainder becomes zero.
36 ÷ 12 = 3 remainder 0
Step 4: Since the remainder is now zero, we stop. The GCD is the last non-zero remainder obtained in Step 3, which is 12.
Below is the C program implementation of the Euclidean Algorithm to find the GCD of two numbers.
//C program to find gcd using Euclidean Algorithm #include <stdio.h> //function to find gcd int gcd(int a, int b) { int temp; while (b != 0) { temp = b; b = a % b; a = temp; } return a; } int main() { int num1, num2; printf("Enter two positive integers: "); scanf("%d %d", &num1, &num2); int result = gcd(num1, num2); printf("The GCD of %d and %d is %d.\n", num1, num2, result); return 0; }
Enter two positive integers: 36 48
The GCD of 36 and 48 is 12.
Time Complexity: O(log(min(a, b))), where 'a' and 'b' are the two input numbers.
Space Complexity: O(1) as a constant amount of space is required to solve this problem.
Approach 2: Brute Force.
In this approach, we find all the divisors of both numbers and then find their common divisors to determine the GCD.
Below is the C program to calculate the GCD of two numbers using for loop.
//C code to find gcd of two numbers using for loop #include <stdio.h> // Function to calculate (GCD) of two numbers int gcd(int a, int b) { // Find the smaller of the two numbers int smaller = (a < b) ? a : b; int result = 1; // Iterate from 1 to the smaller number for (int i = 1; i <= smaller; i++) { // Check if 'i' is a common divisor of both 'a' and 'b' if (a % i == 0 && b % i == 0) { result = i; } } return result; } int main() { int num1, num2; printf("Enter two positive integers: "); scanf("%d %d", &num1, &num2); int result = gcd(num1, num2); printf("The GCD of %d and %d is %d.\n", num1, num2, result); return 0; }
Enter two positive integers: 46 68
The GCD of 46 and 68 is 2.
Time Complexity: O(n), where n is the minimum of the two input numbers.
Space Complexity: O(1), as a constant amount of space is required to solve this problem.
Approach 3: Using Recursion.
It is the recursive version of the Euclidean Algorithm, where the GCD of two numbers is recursively calculated as the GCD of the smaller number and the remainder of the larger number divided by the smaller number.
Example: Find GCD of 48 and 36.
GCD(36, 48) = GCD(48, 36 mod 48) = GCD(48, 12) GCD(48, 12) = GCD(12, 48 mod 12) = GCD(12, 0)
Since the remainder becomes zero in the second step, the GCD is the last non-zero remainder, which is 12. Therefore, the GCD of 36 and 48 is 12.
Below is the recursive C program to find GCD for two numbers.
//C code to find gcd of two numbers using recursion #include <stdio.h> //recursive function int gcd(int a, int b) { //base case if (b == 0) { return a; } return gcd(b, a % b); } int main() { int num1, num2; printf("Enter two positive integers: "); scanf("%d %d", &num1, &num2); int result = gcd(num1, num2); printf("The GCD of %d and %d is %d.\n", num1, num2, result); return 0; }
Enter two positive integers: 60 24 The GCD of 60 and 24 is 12.
Time Complexity: O(log(min(a, b))), where 'a' and 'b' are the two input numbers. The time complexity is determined by the number of recursive calls required to reach the base case.
Space Complexity: O(log(min(a, b))), because each recursive call creates a new activation record (stack frame) to store the function's local variables and return address.
Trends is an amazing magazine Blogger theme that is easy to customize and change to fit your needs.