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 Algorithmrecursive 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++.
Would you like to see your article here on tutorialsinhand.
Join
Write4Us program by tutorialsinhand.com
About the Author
Page Views :
Published Date :
Apr 02,2021