How to find GCD of two numbers in C++
Hello, in this tutorial, we will understand how to find GCD of two numbers in C++ in various ways.
Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two number a and b is the largest number that divides a and b. It is denoted by GCD(a, b).
let’s understand GCD with a simple example
Example : Finding GCD of 24 and 36 24 = 2 × 2 × 2 × 3 × 1 and, 36 = 2 × 2 × 3 × 3 × 1 By compairing each multiplier, we can see that 2 × 2 × 3 are common. Therefore GCD(24,36) = 2 × 2 × 3 = 12
This was the simple approach to find GCD of two numbers. It easy to calculate but, a little bit lengthy in the program. Therefore, we will use Euclid’s approach or (Euclidian Algorithm) to find GCD of two number.
Euclid’s method for finding GCD
The Euclidean method is a technique for quickly finding the GCD of two integers.
In Euclid’s method or Algorithm if we need to find GCD(a, b) and if ‘a’ can be represented as a = bq + r where ‘q‘ is quotient and ‘r‘ is remainder. Then, gcd(a, b) = gcd(b, r). same for b.
Example:
Finding gcd(91, 287): -> First apply the division algorithm for 287 and 91, therefore 287 = 91*3 + 14. -> from the defination, any common divisor of 287 and 91 must also be a divisor of 14, so, d|(287 − 91*3) = 14. -> now, any common divisor of 91 and 14 must also be a divisor of 287. So, gcd(287,91) = gcd(91,14). -> Now, Continuing the process by dividing 91 by 14. so, 91 = 14 * 6 + 7. -> now, we have gcd(91,14)=gcd(14,7), and divide 14 by 7. -> 14 = 7 · 2 + 0 Because 7 divides 14. -> Therefore, gcd(287,91) = gcd(91,14) = gcd(14,7) = 7.
Algorithm to find GCD of two numbers using iteration
- Take input of two numbers in x and y.
- find max(x, y) and save to variable ‘a‘.
- find min(x, y) and save to variable ‘b‘.
- perform iteration for y ≠ 0
(i) save the value of a mod b to ‘r‘
(ii) save the value of b in a and value of r to b. - end the iteration
- print value of a.
C++ program to find the GCD of two numbers using iteration
#include<iostream> using namespace std; int GCD(int, int); int main(){ int y, x; cout<<"Enter the two numbers: "; cin>>x>>y; cout<<"GCD("<< x <<", "<< y <<") = "<< GCD(x, y); return 0; } int GCD(int x, int y){ int a, b, r; if(x > y){ a = x; b = y; } else{ a = y; b = x; } while(b != 0){ r = a % b; a = b; b = r; } return a; }
Output:
Enter the two numbers: 91 287 GCD(91, 287) = 7
Algorithm to find GCD of two numbers using recursion
- Take input of two numbers in x and y.
- call the function GCD by passing x and y.
- Inside the GCD function call the GDC function by passing y and x%y (i.e. GCD(y, x%y) with the base case y = 0. means, if y is eqal to zero then return x.
C++ program: Find GCD using recursion
#include <iostream> using namespace std; int GCD(int, int); int main() { int x , y; cout<<"Enter two number: "; cin>>x>>y; cout<<"GCD("<< x <<", "<< y <<") = "<< GCD(x, y); return 0; } int GCD(int x, int y) { if (y == 0) return x; return GCD(y, x % y); }
Output:
Enter two number: 91 287 GCD(91, 287) = 7
you may also learn:
- Check if a given number is Prime or Composite in C++
- How to Generate a Fibonacci Triangle in C++?
- How to multiply two matrices in C++
how to find GCD(0,3,3,6) => 3
thank you