Articles

# GCD of two numbers in c++ using for loop and euclidean algorithm

In this c++ programs, we will learn to write:

• gcd of two numbers in c++ using for loop
• gcd of two numbers using euclidean algorithm in c++

### GCD of two numbers in cpp or c++

The largest integer which can divide two numbers is the GCD(Greatest Common Divisor) of the numbers.

Simple Solution:

If the two numbers are x and y, we will compare both and store the small value in y. Thereafter a for loop with variable i will run till y with i incrementation. If i values are divided by both x and y then the highest value of i will be gcd of two.

Given below is program for gcd of two numbers in c++ using for loop:

``````#include <iostream>
using namespace std;

int main() {
int x, y, gcd;
cout << "Enter two numbers: ";
cin >> x >> y;

/* Swapping variables x and y if y is greater than x.*/
if ( y> x) {
int t = y;
y= x;
x = t;
}

for (int i = 1; i <=  y; ++i) {
if (x % i == 0 && y % i ==0) {
gcd = i;
}
}

cout << "GCD is: " <<" "<< gcd;
return 0;
}``````

Output:

Enter two numbers: 15 35

GCD is: 5

Time Complexity for gcd of two numbers in cpp: O(n) (n can be compared to y)

Time Complexity:

The number of operations required to achieve any algorithm task.

Efficient Solution:

This Time Complexity can be reduced to in terms of the log by a special algorithm named as "Euclidean Algorithm".

Euclidean Algorithm states that:

If x and y are two numbers then the smaller number is divided, until the remainder is 0. Then the algorithm stops.

Given below is gcd of two numbers using euclidean algorithm in c++:

``````// Euclidean Algorithm-recursive approach
#include<iostream>
using namespace std;
int gcd(int x, int y)
{
if (x == 0)
return y;
return gcd(y % x, x);
}
int main()
{
int a = 10, b = 100;
cout << "GCD = " << gcd(a, b);
return 0;
}``````

Output:

GCD = 10

Time Complexity for gcd of two numbers using euclidean algorithm in c++: O(log(max(x,y)) which can be compared to O(logN)

This completes our article for gcd of two numbers in cpp or gcd of two numbers in c++ using function and gcd of two numbers using euclidean algorithm in c++.

CPP Programs
cpp interview questions

Would you like to see your article here on tutorialsinhand. Join Write4Us program by tutorialsinhand.com 