GCD (Greatest Common Devisior) Algorithms :

We All know what Gcd of two numbers is . There are many questions in which we require to implement the Gcd algorithm . There  are many ways to  find Gcd between two numbers . But we prefer those methods which are more efficient .

 The most basic and best method or algorithm is that one to which we all  are familiar . i.e. Euclid's gcd algorithm :
suppose  there are two numbers a and b of which we need to find the Gcd . We  can implement this either by making a recursive function or by making 'for' loops in your program. But generally recursion is  better than making loops . The code for  the Ecluid's  Gcd goes here :

#include <stdio.h>

int gcd_algorithm(int x, int y)
{
    if (y == 0) {
        return x;
    } else  {
        return gcd_algorithm(y, (x % y));
    }
}

int main(void)
{
    int num1, num2, gcd;
    printf("\nEnter two numbers to find gcd using Euclidean algorithm: ");
    scanf("%d%d", &num1, &num2);
    gcd = gcd_algorithm(num1, num2);
    if (gcd)
        printf("\nThe GCD of %d and %d is %d\n", num1, num2, gcd);
    else
        printf("\nInvalid input!!!\n");
    return 0;
}

  tr to understand this by going step by step in the recursion.

NOW TRY TO FIND GCD OF TWO NUMBERS WHEN ONE OF THEM IS EXTREMELY LARGE :

Suppose numbers  are A and B ,  where A can be  upto 10^250 and B upto 40000 . obviously long long int  can't store A . for better understanding of  this  problem  try  :      https://www.codechef.com/problems/GCD2

  

THERE IS A VERY MISCHIEVOUS METHOD FOR STORING SUCH BIG NUMBERS . WE DO SO BY STORING THEM IN AN ARRAY OF INTEGERS .

FOR EXAMPLE THE ABOVE QUESTION  CAN BE DONE  AS :