Find GCD in C Programming

Introduction

In C programming, GCD (Greatest Common Divisor) is calculated often. Two different ways are commonly used to find GCD. We can use the Euclidean algorithm and calculate GCD by repeated subtraction. In this step-by-step lab, we will demonstrate both methods.

Using Euclidean Algorithm

The Euclidean algorithm, in which the numerator is replaced with the remainder of the division operation, is used to calculate GCD. When the remainder becomes zero, the GCD is the numerator.

1.1 Start the solution by declaring an integer variable named a and b.

    int a, b;

1.2 Next, ask the user to input the values of a and b.

    printf("Enter two numbers: \n");
    scanf("%d %d", &a, &b);

1.3 Then, create a while loop that runs until the remainder of a divided by b is zero.

    while(a!=b)
    {
        if(a>b)
            a=a-b;
        else
            b=b-a;
    }

1.4 Finally, display the GCD of the two numbers.

    printf("The GCD of two numbers is %d", a);

Using Repeated Subtraction Method

In this method, GCD is calculated by repeatedly subtracting the smaller value from the larger value until they become equal. If both of them become equal, then the number is the GCD.

2.1 Begin with an integer variable named num initialised with 0.

    int num = 0;

2.2 Declare an integer variable named x and initialie with 2.

    int x = 2;

2.3 Ask the user to input the number of integers to find the GCD of.

    printf("Enter the number of integers you want to find the GCD of: ");
    scanf("%d", &num);

2.4 Then, ask the user to input the numbers.

    printf("Enter %d numbers:\n", num);
    int arr[num];
    for(int i = 0; i < num; i++)
    {
        scanf("%d", &arr[i]);
    }

2.5 Now we can calculate the GCD by taking input values and using the repeated subtraction method. We will call the function gcd() to calculate the GCD of the input values.

    int result = arr[0];
    for(int i = 1; i < num; i++)
    {
        result = gcd(result, arr[i]);
    }

Combining the Methods

In this step, we will combine the methods to complete the implementation.

3.1 Declare a gcd() function to use in finding GCD by the repeated subtraction method.

    int gcd(int a, int b)
    {
        if(b==0)
            return a;
        else if(a >= b && b > 0)
            return gcd(b,a%b);
        else
            return gcd(b,a);
    }

3.2 Declare a new variable called gcd_result and initialise it to zero.

    int gcd_result = 0;

3.3 We will create a new loop that prompts the user to input numbers until an input value of 0 is detected.

    printf("Enter numbers. To exit enter 0\n");
    while(1)    // infinite loop to take input
    {
        int num;
        scanf("%d", &num);
        if(num < 1)
            break;
        else if(gcd_result == 0)
            gcd_result = num;
        else if(num < gcd_result)
            gcd_result = gcd(num, gcd_result);
        else
            gcd_result = gcd(gcd_result, num);
    }

3.4 Lastly, display the final result using the printf function.

    printf("The GCD of all the entered numbers is: %d\n", gcd_result);

Summary

In this lab, we learned two methods of calculating the GCD of a group of integers in C programming: the Euclidean algorithm and the repeated subtraction method. We demonstrated how to use these methods with a detailed explanation and example code blocks. For further understanding, it is recommended to modify and execute the code in the main.c file.