GCD of Multiple Number

Question

I know how to write a code finding a GCD of 2 number . However, I am trying to solve a problem of finding a GCD of n number and I think the algorithm is a little bit different than using an Eucledian algorithm. My code can be compiled , but it always gave me the wrong result. For example when i put n = 2 , GCD of 16 and 12 it gave the answer 8. Here is my code :

#include<iostream>
using namespace std;
int main()
{
    int a,b[100],c,d,e=0;
    cin>>a;
    for(c=0 ; c<a ; c++)
    {
        cin>>b[c];
    }
    for(c=0 ; c<a-1 ; c++)
    {
        if(c < 1)
        {
            d = b[c]; 
        }
        if(b[c] < d)
        {
            d = b[c];
        }
    }
    while(d>0)
    {
        for(c=0 ; c<a ; c++)
        {
            if(b[c] % d < 1)
            {
                e++;
            }
        }
        if(e == c)
        {
            cout<<d;
            break;
        }
        d--;
    }
}

Can you guys please find the mistake in my code?

You have made this way too complicated. To find the GCD of two numbers, use: `int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }` — Cody Gray - on strike, Jul 03 '16 at 14:08
@CodyGray I am actually trying to find the GCD of more than 2 numbers in here — , Jul 04 '16 at 05:53
Yes, I got that, but it doesn't justify the complication of your code. Finding the GCD of 2+n numbers is just an iteration on finding the GCD of 2 numbers. — Cody Gray - on strike, Jul 04 '16 at 11:30

DarthGizka · Accepted Answer · 2018-09-17T20:05:12.623

Your code does not compute the greatest common divisor of the input array - it counts how many of the entries are evenly divisible by the smallest element d of the array, then how many are divisible by one smaller, and so on until d is 0. This has nothing to do with the GCD at all.

One easy way - though not necessarily the fastest - would be based on the fact that the GCD of three numbers must be the same as the GCD of any one of those numbers and the GCD of the other two.

gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) = gcd(gcd(a, c), b)

Extension to n inputs is elementary:

int result = a[0];

for (int i = 1; i < a.Length; ++i)
    result = gcd(result, a[i]);

Code for the GCD of two numbers can be found all over the 'net, for example at Rosetta Code. One of my favourites is this plain iterative version:

int gcd (int a, int b)
{
    while (b)
    {
        int t = b;
        b = a % b;
        a = t;
    }

    return a;
}

C# allows a more succinct formulation but in other languages this probably won't work (in C++ it would invoke undefined behaviour, for example):

static int gcd (int a, int b)
{
    while (b != 0)
        b = a % (a = b);

    return a;
}

In your last code snippet, the value of a is modified without a [sequence point](http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points), which invokes undefined behavior. You've made the code a bit *too* simple. — Cody Gray - on strike, Jul 03 '16 at 14:40
@Cody: I've changed it to a version that works in languages other than C#, since the topic is tagged [tag:C++] (where the original code would have invoked undefined behaviour). — DarthGizka, Jul 03 '16 at 14:45
Oh I found the mistakes guys , it's actually because my variable **e** but i've fixed it and it shows me the right results. I'm sorry to even post this here because of my silly mistake — , Jul 04 '16 at 06:09

score 0 · Answer 2 · answered Jun 04 '18 at 23:48

In case some find it helpful, here is an implementation of the Euclidean algorithm in JavaScript.

function EuclideanGCD(a, b) {

  // Make sure a > b, interchange values
  if (a < b) {
    c = a;
    a = b;
    b = c
  }

  // If A = 0 then GCD(A,B) = B  and we can stop.  
  if (a == 0) {
    return b;

  // If B = 0 then GCD(A,B) = A  and we can stop.  
  } else if (b == 0) {
    return a;
  } else {

    let gdc = 0;
    let quotient = Math.floor(a / b); // Get the divisor
    let remainder = a % b; // Get the remainder

    // Make a recursive call, till we hit 0
    gdc = EuclideanGCD(b, remainder);
    return gdc;
  }

}

var gcd = EuclideanGCD(234, 357); 
console.log(gcd); // Outputs: 3

GCD of Multiple Number

2 Answers2