GCD of two numbers in C++
In this article, you will learn to find the greatest common divisor (G.C.D) or highest common factor (H.C.F) of numbers using different methods using the C++ programming.
Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted gcd(a,b). These are different ways to find the GCD or HCF using C++ -
GCD in C++ using for loop
Here, we define a function to compute the G.C.D of two numbers, num1 and num2 and return it. In each iteration, we check if our number perfectly divides both the given numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.
#include <iostream>
using namespace std;
int main() {
int num1, num2, i, gcd;
cout << "Enter two positive numbers: ";
cin << num1 << num2;
for (i = 1; i <= num1 && i <= num2; ++i) {
if (num1 % i == 0 && num2 % i == 0) {
gcd = i;
}
}
cout << "\nThe GCD number of " << num1 << " & " << num2 << ": " << gcd << "\n";
return 0;
}
Output of the above code:
Enter two positive numbers: 32 89
The GCD number of 32 & 89: 1
Enter two positive numbers: 24 42
The GCD number of 24 & 42: 6
GCD in C++ using while loop
In the given C program, we have used the while loop to find the G.C.D of two numbers. In this method, the smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding the larger integer. This process is continued until the condition num1!=num2 becomes false.
#include <iostream>
using namespace std;
int main() {
int num1, num2;
cout << "Enter two numbers: ";
cin << num1 << num2;
while(num1 != num2) {
if(num1 > num2)
num1 -= num2;
else
num2 -= num1;
}
cout << "GCD = " << num1;
return 0;
}
Output of the above code:
Enter two numbers: 78 47
GCD = 1
Enter two numbers: 27 24
GCD = 3
GCD in C++ using recursion
Recursion function is a function which is calling itself. The following code finds the greatest common divisor of user inputs using the recursion function. A recursion function continues until some condition is met to prevent it. That's why we use the if statement to break the infinite recursion.
#include <iostream>
using namespace std;
int compute_gcd(int x, int y) {
if (y != 0)
return compute_gcd(y, x % y);
else
return x;
}
int main() {
int num1, num2;
cout << "Enter two numbers: ";
cin >> num1 >> num2;
// Calling function compute_gcd()
cout << "\nGCD = " << compute_gcd(num1, num2);
cout << endl;
return 0;
}
Output of the above code:
Enter two numbers: 87 27
GCD = 3
Related Articles
Queue implementation in c++Queue using linked list c++
Swapping of two numbers in C++
Generate random numbers in C++
C program to convert celsius to fahrenheit
Fibonacci series program in C using recursion
Write a program to find area of circle in C
C program to find greatest of three numbers
C program for addition of two numbers
C program to calculate compound interest
C program to find the ASCII value of a character
C program to convert Decimal to Octal
C program to convert decimal to binary
Write a C program to calculate Simple Interest
C program to check whether a number is even or odd
C program to reverse a number
C program to check palindrome number
C program to check whether an alphabet is a vowel or consonant
Program to find square root of a number in C
C program to check whether a number is positive or negative