C Program to Find GCD of N Numbers

programming

Problem: Write a C program to find GCD of n numbers or array of n numbers.

Recommended: GCD of Two Numbers in C

Greatest Common Divisor (GCD) of two or more numbers is the largest possible integer that can divide each of the numbers.

For example, GCD of 15, 10, and 20 is 5.

The trick to find GCD of more than two numbers is to use the GCD of two numbers with the third one.

For example, we will first calculate the GCD of the first two numbers of the array (say x), then we will calculate the GCD of the x and the third number, (say y) then again we will compute the GCD of y and the fourth number.

We will repeat this process until the last element of the array and the final GCD value would be the GCD of the whole array.

Here is the implementation of the above algorithm in C.

#include <stdio.h>
int findGCD(int, int);

int main() {
    int array[] = {15, 10, 20, 25};
    int gcd = array[0];
 
    //Reuse the previous calculated GCD value
    for(int i=1; i<4; i++){
      gcd = findGCD(array[i], gcd);
    }
    
    printf("GCD: %d", gcd);
}

//Recursive function to find GCD of two numbers
int findGCD(int a, int b){
    if(b == 0)
      return a;
    return findGCD(b, a%b);
}

Output

GCD: 5

In this example, we learned to find GCD of n numbers or array of n numbers in C programming language.

Leave a Reply

Your email address will not be published. Required fields are marked *