C++ program to find the greatest common divisor (GCD)

Posted by admin January 9, 2023

Source Code

#include <iostream>

using namespace std;

int main()
{
    int a, b; // Declare variables to hold the two numbers

    cout << "Enter the first number: "; // Prompt the user to enter the first number
    cin >> a; // Read the first number from the standard input stream

    cout << "Enter the second number: "; // Prompt the user to enter the second number
    cin >> b; // Read the second number from the standard input stream

    // Find the GCD of the two numbers using the Euclidean algorithm
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }

    cout << "The GCD of the two numbers is: " << a << endl; // Print the GCD

    return 0;
}

Code Explanation

This program declares variables a and b of type int to hold the two numbers entered by the user. It then uses the cout object to print prompts asking the user to enter the two numbers and the cin object to read the numbers from the standard input stream.

To find the GCD of the two numbers, the program uses the Euclidean algorithm, which is an efficient method for finding the GCD of two numbers. The algorithm works by repeatedly dividing the larger number by the smaller number, and taking the remainder as the new smaller number. This process is repeated until the smaller number becomes 0, at which point the larger number is the GCD.

The program uses a while loop to implement the Euclidean algorithm. The loop continues as long as the smaller number (b) is not 0. On each iteration, the smaller number (b) is updated to the remainder of the division of the larger number (a) by the smaller number (b), and the larger number (a) is updated to the value of the smaller number (b) before the update.

Finally, the program uses the cout object to print the value of a, which is the GCD of the two numbers.

Explain greatest common divisor (GCD)

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides all of the integers without leaving a remainder. It is also known as the greatest common factor (GCF) or the highest common factor (HCF).

For example, the GCD of 8 and 12 is 4, since 4 is the largest positive integer that divides both 8 and 12 without leaving a remainder. The GCD of 24 and 36 is 12, since 12 is the largest positive integer that divides both 24 and 36 without leaving a remainder.

Note: C++ All Examples

Tags: