Question

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

Answer 1

#include <iostream>

// Function to calculate GCD using iteration
int compute_gcd(int a, int b) {
    int gcd;
    for (int i = 1; i <= a && i <= b; i++) {
        if (a % i == 0 && b % i == 0)
            gcd = i;
    }
    return gcd;
}

int main() {
    // Declare and initialize two numbers
    int a = 12, b = 20;

    // Call the function to compute GCD
    int gcd = compute_gcd(a, b);

    // Output the GCD
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << gcd;

    return 0; 
}

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

 

Learn SQL from A to Z at LearnSQL.com

Answer 2

#include <iostream>

// Function to calculate GCD using iteration
int compute_gcd(int a, int b) {
    int i = a < b ? a : b;
     
    for (; i >= 1; i--) { // Iterate downward to find the largest common divisor
        if (a % i == 0 && b % i == 0) {
            return i; // Return the first found GCD
        }
    }
     
    return 1; // Default return if no common divisor is found
}

int main() {
    // Declare and initialize two numbers
    int a = 12, b = 20;

    // Call the function to compute GCD
    int gcd = compute_gcd(a, b);

    // Output the GCD
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << gcd;

    return 0; 
}

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

 

Learn SQL from A to Z at LearnSQL.com

Answer 3

#include <iostream>

// Function prototype for computing the greatest common divisor (GCD)
int gcd(int a, int b);

int main() {
    // Declare and initialize two numbers
    int a = 12, b = 20;
     
    // Call the gcd function and store the result
    int _gcd = gcd(a, b);
   
    // Output the greatest common divisor (GCD)
    std::cout << "The GCD (greatest common divisor) of " << a << " and " << b << " is: " << _gcd;

    return 0; 
}

// Recursive function to compute the GCD
int gcd(int a, int b) {
    // Base case: if b is 0, return a as the GCD
    return b == 0 ? a : gcd(b, a % b); // Recursive call with b and remainder of a divided by b
}

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

 

Learn SQL from A to Z at LearnSQL.com

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 SQL from A to Z at LearnSQL.com

Answer 5

#include <iostream>

// Function to compute the greatest common divisor (GCD) using the Euclidean algorithm
int GCD(int a, int b) {
    // Ensure 'a' is greater than 'b' by swapping if necessary
    if (b > a) {
        std::swap(a, b);
    }
    
    // Iteratively calculate the GCD using the Euclidean method
    while (b != 0) {
        int tmp = a % b; // Compute remainder of 'a' divided by 'b'
        a = b; // Update 'a' to be the previous 'b'
        b = tmp; // Update 'b' to be the remainder
    }

    return a; // Return the computed GCD
}

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

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

    return 0; 
}

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

 

Learn SQL from A to Z at LearnSQL.com

Answer 6

#include <iostream>
#include <numeric>
   
int main()
{
    int a = 12, b = 20;
     
    auto 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 SQL from A to Z at LearnSQL.com