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++.