Question

How to calculate the GCD (greatest common divisor) of two integers in C++

Answer 1

#include <iostream>
 
int main()
{
    int a = 12 , b = 20, gcd;
 
    for (int i = 1; i <= a && i <= b; i++) {
        if (a % i == 0 && b % i == 0)
            gcd = i;
    }
 
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << gcd;
}
 
 
 
 
/*
run:
 
The GCD (greatest common divisor) of 12 and 20 is: 4
 
*/

 

Learn & Practice Python
with the most comprehensive set of 13 hands-on online Python courses
Start now

Answer 2

#include <iostream>
 
int main()
{
    int a = 12, b = 20, gcd;
 
    int i = a < b ? a : b;
 
    for (;i <= a && i <= b; i--) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
            break;
        }
    }
 
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << gcd;
}
 
 
 
 
/*
run:
 
The GCD (greatest common divisor) of 12 and 20 is: 4
 
*/

 

Learn & Practice Python
with the most comprehensive set of 13 hands-on online Python courses
Start now

Answer 3

#include <iostream>

int gcd(int a, int b);
  
int main()
{
    int a = 12, b = 20;
    
    int _gcd = gcd(a, b);
  
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << _gcd;
}
  
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
  
  
  
  
/*
run:
  
The GCD (greatest common divisor) of 12 and 20 is: 4
  
*/

 

Learn & Practice Python
with the most comprehensive set of 13 hands-on online Python courses
Start now

Answer 4

#include <iostream>
#include <algorithm>
  
int main()
{
    int a = 12, b = 20;
    
    int gcd = std::__gcd(a, b); 
  
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << gcd;
}
 
  
  
  
/*
run:
  
The GCD (greatest common divisor) of 12 and 20 is: 4
  
*/

 

Learn & Practice Python
with the most comprehensive set of 13 hands-on online Python courses
Start now

Answer 5

#include <iostream>

int GCD(int a, int b) {
    if ( b > a) {
        std::swap(a,b);
    }
    
    while (b != 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }

    return a;
}

int main()
{
    int a = 12 , b = 20;

    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << GCD(a, b);
}

  
  
/*
run:
  
The GCD (greatest common divisor) of 12 and 20 is: 4
  
*/

 

Learn & Practice Python
with the most comprehensive set of 13 hands-on online Python courses
Start now