This blog is under construction

Friday, 12 July 2013

C program to calculate GCD of n numbers

Write a C program to calculate GCD of n numbers.


  #include <stdio.h>
  #include <stdlib.h>

  int main() {
        int i, j, n, flag = 0, small, *data;

        /* get the number of inputs from the user */
        printf("Enter the number of inputs:");
        scanf("%d", &n);

        /* allocate memory to store n numbers */
        data = (int *)malloc(sizeof(int) * n);

        /* get n numbers from the user */
        for (i = 0; i < n; i++) {
                printf("Data[%d]: ", i);
                scanf("%d", &data[i]);
        }

        /* find the smallest of n numbers */
        small = data[0];
        for (i = 1; i < n; i++) {
                if (data[i] < small)
                        small = data[i];
        }

        /*
         * use the smallest no to find gcd of n numbers.
         * Start checking from small to 1 whether the 
         * same value divides all the given inputs
         */
        for (i = small; i > 0; i--) {
                for (j = 0; j < n; j++) {
                        if (data[j] % i != 0) {
                                flag = 1;
                        }
                }
                /* print the result */
                if (!flag) {
                        printf("GCD of given %d numbers is %d\n", n, i);
                        break;
                }
                flag = 0;
        }

        return 0;
  }



  Output:
  jp@jp-VirtualBox:~/$ ./a.out
  Enter the number of inputs:5
  Data[0]: 144
  Data[1]: 180
  Data[2]: 108
  Data[3]: 117
  Data[4]: 135
  GCD of given 5 numbers is 9



3 comments:

  1. I think in the 'j' loop when the condition arr[j] % i != 0 is satisfied you should break from the loop there only. It is performing unnecessary computations after that.

    ReplyDelete
  2. I hope to really understand for this information.Thanks a lot.

    Manpower Consultancy in Chennai

    ReplyDelete
  3. Great content thanks for sharing this informative blog which provided me technical information keep posting.
    c,c++ training in chennai

    ReplyDelete