Finding the greatest common divisor of an array of integers in C using the Divide and Conquer method

If you want to know more about the greatest common divisor of two numbers, reading this article first may prove helpful.


The following C function finds the greatest common divisor of a set of integers using the Divide et Impera method and returns it.

/*
 * Description:
 *  Finds the greatest common divisor of an array of integers
 * Parameters:
 *  a     - the array
 *  first - the index of the leftmost elements of the array
 *  last  - the index of the rightmost element of the array
 * Returns:
 *  gcd - the greatest common divisor
 */
int ArrayGCD(int *a, int first, int last)
{
    int x = 0, y = 0, gcd = 0;
    if(first == last)
    {
        gcd = a[first];
        return gcd;
    }
    else
    {
        x = ArrayGCD(a,first,(first+last)/2);
        y = ArrayGCD(a,(first+last)/2+1,last);
        if(x < 0)
        {
            x = -x;
        }
        if(y < 0)
        {
            y = -y;
        }
        while(x != y)
        {
            if(x > y)
            {
                x = x-y;
            }
            else
            {
                y = y-x;
            }
        }
        gcd = x;
        return gcd;
    }
}

Example:

#include<stdio.h>
#include<conio.h>

int ArrayGCD(int *a, int first, int last);

int main(void)
{
    int a[20], n = 0, i = 0, gcd = 0;
    printf("\n Enter the number of elements of the array: ");
    scanf("%d",&n);
    printf(" Enter the elements of the array:\n");
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    gcd = ArrayGCD(a,0,n-1);
    printf("\n\tThe greatest common divisor is: %d",gcd);
    getch();
    return 0;
}

Output: