# C++ Program - Find GCD of Two Numbers

**GCD** stands for **Greatest Common Divisor**. The GCD of two numbers is the largest number that divides both of them.

For example - GCD of 20 and 25 is 5, and GCD of 50 and 100 is 50.

### Method 1: Using For Loop to find GCD of two numbers

In the below example, for loop is used to iterate the variable *i* from 0 to the smaller number. If both numbers are divisible by *i*, then it modifies the GCD and finally gives the GCD of two numbers.

#include <iostream> using namespace std; int main() { int x = 50; int y = 100; int temp, gcd; if (x > y) { temp = x; x = y; y = temp; } for(int i = 1; i < (x+1); i++) { if (x%i == 0 && y%i == 0) gcd = i; } cout<<"GCD of "<<x<<" and "<<y<<" is: "<<gcd; return 0; }

The above code will give the following output:

GCD of 50 and 100 is: 50

### Method 2: Using While Loop to find GCD of two numbers

In the below example, larger number is replaced by a number which is calculated by subtracting the smaller number from the larger number. The process is continued until the two numbers become equal which will be GCD of two numbers.

#include <iostream> using namespace std; int main() { int p, q, x, y; p = x = 20; q = y = 25; while (x != y) { if (x > y) x = x - y; else y = y - x; } cout<<"GCD of "<<p<<" and "<<q<<" is: "<<x; return 0; }

The above code will give the following output:

GCD of 20 and 25 is: 5

### Method 3: Using the recursive function to find GCD of two numbers

In the below example, recursive function is used. In this method, instead of using subtraction operator(as in above example), modulus operator is used. This method is also known as **Euclidean algorithm**.

#include <iostream> using namespace std; int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x%y); } int main() { int x = 250; int y = 475; cout<<"GCD of "<<x<<" and "<<y<<" is: "<<gcd(x,y); return 0; }

The above code will give the following output:

GCD of 250 and 475 is: 25

### Method 4: Using __gcd() function of <algorithm> header file

C++ has in-built function __gcd() in <algorithm> header file which can be used to calculate GCD of two numbers. The syntax for using this function is given below:

//returns 0 if both x and y are zero, //else returns gcd of x and y __gcd(x,y);

Consider the following example:

#include <iostream> #include <algorithm> using namespace std; int main() { int x = 100; int y = 150; cout<<"GCD of "<<x<<" and "<<y<<" is: "<<__gcd(x,y); return 0; }

The above code will give the following output:

GCD of 100 and 150 is: 50

### Recommended Pages

- C++ Program - To Check Prime Number
- C++ Program - Bubble Sort
- C++ Program - Selection Sort
- C++ Program - Maximum Subarray Sum
- C++ Program - Reverse digits of a given Integer
- C++ - Swap two numbers
- C++ Program - Fibonacci Sequence
- C++ Program - Insertion Sort
- C++ Program - Find Factorial of a Number
- C++ Program - Find HCF of Two Numbers
- C++ Program - Merge Sort
- C++ Program - Shell Sort
- Stack in C++
- Queue in C++
- C++ Program - Find LCM of Two Numbers
- C++ Program - To Check Whether a Number is Palindrome or Not
- C++ Program - To Check Whether a String is Palindrome or Not
- C++ Program - Heap Sort
- C++ Program - Quick Sort
- C++ - Swap Two Numbers without using Temporary Variable