C program to find GCD of two numbers
Introduction
The greatest common divisor (GCD) between the two supplied numbers is determined by this program. The greatest integer that divides the two provided numbers equally is represented by the GCD.
For instance, the largest integer that is capable of dividing both 12 and 16 without leaving a residual is 4, which is the GCD when looking at the numbers 12 and 16.
The GCD is computed by the program using the Euclidean algorithm. Finding the greatest common divisor of the remainder and the divisor again is how the recursive Euclidean algorithm operates.
When the remainder is 0, the procedure stops, and the GCD of both numbers serves as the divisor.
Python was used to create the program. It accepts two distinct numbers as inputs and displays their GCD.
What exactly is the GCD?
The largest positive integer that evenly divides both a and b, represented as a and b, is known as the greatest common divisor (GCD) of two integers.
For instance, the GCD of the integers 12 and 16 is 4, which is the largest number that can divide them equally.
The Euclidean algorithm, a recursive procedure that finds the greatest common divisor between the remainder and the divisor repeatedly, can be used to determine the GCD. When the remainder is 0, the procedure stops, and the GCD of the two numbers serves as the divisor.
There are numerous uses for the GCD in both math and computer science. It can be used, for instance, to resolve issues with divisibility, cryptography, and number theory.
C program to find GCD of two numbers:
#include <stdio.h>
int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
int main() {
int n1, n2;
printf("Enter 2 nums: ");
scanf("%d %d", &n1, &n2);
int res = gcd(n1, n2);
printf("The GCD of %d and %d is %d.\n", n1, n2, res);
return 0;
}
Output:
![C program to find GCD of two numbers](https://static.tutorialandexample.com/c/c-program-to-find-gcd-of-two-numbers1.png)
Euclidean Algorithm:
A recursive procedure known as the Euclidean algorithm can be used to determine the GCD of two numbers. It is the most effective approach for figuring out the GCD and is employed in a wide range of mathematical and computer science fields.
Iteratively calculating the GCD between the amount left over and the divisor is a step in the Euclidean algorithm. When the remainder is 0, the procedure stops, and the GCD of both numbers serves as the divisor.
A quick and accurate calculation of the greatest common divisor (GCD) among two numbers is possible thanks to the Euclidean algorithm. It is utilized in numerous branches of mathematics and computer science and is simple to comprehend and apply.
The following are a few uses for the Euclidean algorithm:
- Dividing difficulties and their solutions
- Secret-keeping Number theory
- Geometry
- Science of computers
- A versatile tool, the Euclidean algorithm is effective in solving a wide range of issues. For any mathematical expert or computer scientist, it is a useful tool.
The greatest common divisor (GCD) of two numbers can be discovered using a variety of techniques. Among the most popular techniques are:
The Euclidean technique is the most effective way to compute the GCD. Finding the GCD of the rest of the number and the divisor repeatedly is how it operates. When the remainder is 0, the procedure stops, and the GCD of the two numbers serves as the divisor.
Long division: This is an easier way to figure out the GCD. The formula involves dividing the larger by the smaller integer and recording the remainder. After then, until there is no more remainder, the remainder is divided by the smaller number once again. The GCD of the is the denominator at this time.
Prime Factorisation: The two numbers are factored into their prime components in order for this technique to function. The GCD is then calculated by multiplying the prime factors that both numbers share.
Eratosthenes' Sieve Making a list of all prime numbers up to a particular amount is how this method operates. Then, by comparing the prime factors of two numbers to the set of prime numbers, one can determine the GCD of those numbers.
The particular numbers at play determine the optimal procedure to employ for determining the GCD. The most effective technique is the Euclidean algorithm, but it might be more challenging to comprehend and use. Although the long division method is simpler, it is less effective. Although the technique of prime factorization is more versatile, it can take longer. For locating large prime numbers, the sieve of Eratosthenes is more effective, but it is less effective for locating small prime numbers.
The many techniques for locating the GCD are listed in the following table:
1. Method: Euclidean algorithm
- Efficiency: Most efficient
- Complexity: O(log n)
- Understanding: Difficult
2. Method: Prime factorization
- Efficiency: General
- Complexity: O(n logn)
- Understanding: Easy
3. Method: Long division
- Efficiency: Basic
- Complexity: O(n)
- Understanding: Easy
4. Method: Sieve of Eratosthenes
- Efficiency: Efficient for large prime numbers
- Complexity: O(n log log n)
- Understanding: Difficult