c++ Greatest Common Divisor

Question

I am very new to C++ and am attempting create a function to implement the Euclidean algorithm that returns the greatest common divisor for two integer inputs.

The current approach I am taking keeps crashing - can you help me understand why?

int main() {    
    int a = 0;
    int b = 0;

    cin >>  a;
    cin >> b;

    do {
        if ( a > b ) a = a % b;
        else if ( a < b ) b = b % a;
        else if ( a == b ) break;
    } while ( ( a || b ) != 0 ); 

    return 0;
}

Thanks,

David

Armen Tsirunyan · Accepted Answer · 2015-03-10T20:24:41.770

12

while ( ( a || b ) != 0 );

this is wrong. It should be

while ( a != 0 && b != 0 );

On a side note, the Euclid's algorithm can be concisely implemented recursively:

int gcd(int a, int b)
{
   return b == 0 ? a : gcd(b, a%b);
}

edited Mar 10 '15 at 20:24

answered Mar 10 '15 at 20:19

Armen Tsirunyan

130,161
59
324
434

1

http://www.nullptr.me/2012/01/07/c-template-metaprogramming/ there are a couple of GCD implementations. also recursive. – Alexander Oh Mar 10 '15 at 20:54

FireRain · Answer 2 · 2015-03-10T20:25:56.897

3

Your term ( a || b ) != 0 will not resolve as you expect.
What you want to do is (a != 0) && (b != 0)
Or as Cheers and hth. - Alf suggests just a && b.

edited Mar 10 '15 at 20:25

answered Mar 10 '15 at 20:19

FireRain

103
8

2

why not just `a && b` – Cheers and hth. - Alf Mar 10 '15 at 20:20
@Cheersandhth.-Alf This might be less readable/understandable for new C++ learners. – frogatto Mar 10 '15 at 20:30
@abforce you're right i don't get `a && b` can you explain? – David Loughnane Mar 10 '15 at 20:51
1

@DavidLoughnane `a && b` is evaluated to `true` when both `a` and `b` have non-zero values. – frogatto Mar 10 '15 at 20:58

score 1 · Answer 3 · edited May 23 '17 at 11:51

1

Your while condition is wrong. You cant simplify it like that.

while ( ( a || b ) != 0 );

It should look like this.

while ( ( a != 0 ) && ( b != 0 ) );

By the way, you could make an much easier approach. Something like this

int main() {

int a, b, r;

cin >> a;
cin >> b;

while ( b != 0) {
    r = a % b;
    a = b;
    b = r;
}

cout << "The GCD is " << a << endl;

}

And there is another way, it doesnt requiere code the algorithm. Just use the libstdc++ algorithm library. Libstdc++

edited May 23 '17 at 11:51

Community

1
1

answered Mar 10 '15 at 20:42

Enpi

281
1
9

made the same program... you also could have written while (b) instead of while (b !=0). But either way.. very cool use of the Euclidian algorithm! – moldovean May 15 '15 at 17:57

score 1 · Answer 4 · answered Mar 10 '15 at 21:21

Let's have a closer look at your codes, maybe you are curious what does while ( ( a || b ) != 0 ) do?

We now should evaluate ( a || b ) != 0. In C/C++ evaluation begins from right to left, but () has more priority, so at run-time we would have:

bool r1 = a || b;  // intermediate result
bool r2 = r1 != 0;
while(r2);

Steps:

a || b is evaluated to true when either a or b have non-zero value.
r1 will be casted to integer
- true becomes 1
- false becomes 0
r1 != 0 is evaluated and results an boolean value (true or false)
while decides whether it should loop or not.

c++ Greatest Common Divisor

4 Answers4