GCD of 3 numbers · DIGIT-ARC

K

//Find GCD of three numbers
#include<iostream.h>
#include<conio.h>

void main()
{
int a,b,c,i,j,m;
cout<<"Enter the values";
cin>>a>>b>>c;
if(a>b)
{
if(a>c)
{
m=a;
}
else
{
m=c;
}
}
else
{
if(b>c)
{
m=b;
}
else
{
m=c;
}
}
j=0;
for(i=m;i>=2;i--)
{
if(a%i==0 && b%i==0 && c%i==0)
{
j++;
break;
}
}
if(j==0)
cout<<"GCD is 1";
else
cout<<"GCD is"<<i;
getch();
}

whats wrong in this code?? My teacher says logic I have used is wrong

You should use the Euclidean algorithm to find GCD, its much easier and faster that way. Since you would use the remainders got by dividing one number by another and find the GCD (final remaining remainder).

Here's the implementation in Standard C++ code:

Code:

#include<iostream>

using namespace std;

int gcd(int a, int b)
{
    int t;
    
    while(b!=0)
    {
        t = b;
        b = a%b; // B's now the remainder of A/B.
        a = t;
    } // And we go to the next iteration.
    
    return a;
}

int main()
{
    int a,b,c,g;
    cout<<"Enter 3 numbers: ";
    cin>>a>>b>>c;
    [B]g=gcd(gcd(a,b),c);[/B] // Comm./Asso. laws...
    cout<<"The GCD of the 3 numbers is: "<<g<<endl;
    return 0;
}

Your way takes some extra number crunching and thus its way slow for large numbers.

Apart from that, it sure is correct in its answer. Your teacher is probably acting oversmart.

Lets try an example of 12121212, 18181818, 24242424

Time taken

Code:

bigbang@pysnakums:~$ time ./yours
GCD is
6060606

real    0m0.[B]271s[/B]
user    0m0.272s
sys     0m0.000s

bigbang@pysnakums:~$ time ./euclid
The GCD of the 3 numbers is: 6060606

real    0m0.[B]003s[/B]
user    0m0.004s
sys     0m0.000s

K

Thanks