gcd of two numbers c++
To find the greatest common divisor (gcd) of two numbers in C++, you can use the Euclidean algorithm. Here's how you can implement it step by step:
Include the necessary header file: Begin by including the
<iostream>
header file, which will allow you to use input and output stream operations in your program.Declare the function: Declare a function called
gcd
that takes two integer parameters,a
andb
, and returns an integer.Write the base case: In the
gcd
function, write a base case that checks ifb
is equal to 0. If it is, return the value ofa
as the gcd.Use recursion: If
b
is not equal to 0, use recursion to call thegcd
function again, but withb
as the new value ofa
and the remainder ofa
divided byb
as the new value ofb
.Return the result: Finally, return the result of the recursive call as the gcd of the two numbers.
Here's an example implementation of the gcd function in C++:
#include <iostream>
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int num1, num2;
std::cout << "Enter two numbers: ";
std::cin >> num1 >> num2;
std::cout << "The gcd is: " << gcd(num1, num2) << std::endl;
return 0;
}
In this example, the main
function prompts the user to enter two numbers, and then calls the gcd
function to calculate and display the gcd of the two numbers. The gcd
function uses the Euclidean algorithm recursively to find the gcd.