Tag: Euclid’s algorithm

Write a function to compute the greatest common divisor given by Euclid’s algorithm, exemplified for J = 1980, K = 1617 as follows:

Thus, the greatest common divisor is 33.

Analyze Above Problem Statement

1. We need to find Greatest Common Divisor(GCD) of 2 numbers entered by the user, using Euclid’s Algorithm.

2. If J = 1980 and K = 1617, GCD should be 33.

3. Make sure to use the calculation part as shown in problem statement.

4. We observe the calculation part in problem statement and formulate some formulas to figure out the result i.e., GCD of 2 numbers input by the user.

Related Read:
C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm

Video Tutorial: C Program To Find GCD using Pointers and Functions, using Euclid’s Algorithm

Source Code: C Program To Find GCD using Pointers and Functions, using Euclid’s Algorithm

#include<stdio.h>

void calc_gcd(int, int, int*);

int main()
{
    int j, k, gcd;

    printf("Enter 2 integer numbers\n");
    scanf("%d%d", &j, &k);

    calc_gcd(j, k, &gcd);

    printf("\nGreatest Common Divisor of %d and %d is %d.\n", j, k, gcd);

    return 0;
}

void calc_gcd(int numerator, int denominator, int *gcd)
{
    int temp, num;

    if(denominator == 0)
    {
        *gcd = numerator;
    }
    else if(numerator == 0)
    {
        *gcd = denominator;
    }
    else
    {
        num  = numerator / denominator;
        temp = numerator - num * denominator;

        while(temp)
        {
            numerator   = denominator;
            denominator = temp;
            num  = numerator / denominator;
            temp = numerator - num * denominator;
        }

        *gcd = denominator;
    }
}

Output 1:
Enter 2 integer numbers
1980
1617

Greatest Common Divisor of 1980 and 1617 is 33.

Output 2:
Enter 2 integer numbers
1617
1980

Greatest Common Divisor of 1617 and 1980 is 33.

Output 3:
Enter 2 integer numbers
15
20

Greatest Common Divisor of 15 and 20 is 5.

Output 4:
Enter 2 integer numbers
20
15

Greatest Common Divisor of 20 and 15 is 5.

Logic To Find GCD using Pointers and Functions, using Euclid’s Algorithm

We ask the user to input integer values for variables j and k. We pass values of j and k and address of variable gcd to a function called calc_gcd().

Inside calc_gcd() function
Inside calc_gcd() function we use the following calculations:

Note: We copy the value of j, k and &gcd passed by main method into local variables of calc_gcd() i.e., numerator, denominator and *gcd.

Step 1: We check if denominator is 0. In that case the value present in numerator itself is the GCD. So we copy value present in variable numerator to *gcd.

Step 2: If denominator is not zero. Then, we divide numerator with denominator value and store the result into a variable called num.

num = numerator / denominator;

If j = 1980 and k = 1617, then numerator = 1980 and denominator = 1617.

num = numerator / denominator;
num = 1980/ 1617;
num = 1;

According to problem statement:

We’ve formulated the equation for the first part i.e., 1980 / 1617 = 1
Now lets formulate an equation for the second part i.e., 1980 – 1 * 1617 = 363

If you look at 1980 – 1 * 1617 = 363 closely and substitute the values with corresponding variables then you’ll come up with below formula:

temp = numerator – num * denominator;

Look at Step 1 for values of numerator, denominator and num.

Now lets look at the equations given in the problem statement:

In this look at 1617 / 363 = 4. Here the value of denominator has been shifted to numerators place, and the value of temp has been copied to denominator. So lets write the code:

numerator = denominator;
denominator = temp;

Step 3: Now lets use these formulate in co-ordination to finish writing our function code.

We need to repeat the code in order to get the results according to the columns present in the problem statement equations:

Here are our formulas:

   
        num         = numerator / denominator;
        temp        = numerator - num * denominator;     
        numerator   = denominator;
        denominator = temp;

Here are the steps in problem statement to calculate the GCD:

We need to repeat execution of our code to get above result:

num  = numerator / denominator;
temp = numerator - num * denominator;

     while(temp)
     {
        numerator   = denominator;
        denominator = temp;
        num  = numerator / denominator;
        temp = numerator - num * denominator;
      }

      *gcd = denominator;

We need to put our code inside a looping construct to repeat the code. Here we are using while loop. So while loop iterates until temp value is positive. Once value of temp is 0, the control exits the while loop.

We have written 2 lines of code before the while loop:

num  = numerator / denominator;
temp = numerator - num * denominator;

that is because we need to have some value inside variable temp before using it as condition for while loop.

Once the value of temp is 0, control exits while loop. Outside while loop we transfer the value present inside denominator to *gcd.

So *gcd will have the Greatest Common Divisor for values input by the user(j = 1980 and k = 1617).

Observe this table from problem statement

When temp value is 0, value of denominator is 33 – which is the Greatest Common Divisor of numbers 1980 and 1617.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert