Tuesday, July 16, 2013

How to find Greatest Common Divisor in C++

#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int, int);
int main(){
    int x,y;
    while(cin>>x>>y){
        int res = gcd(x, y);
        cout<<"The GCD of x and y is: "<<res<<endl;
    }
    return 0;
}

int gcd(int x, int y){
    int q, r, r1, r2;
    if(x == 0) return y;
    if(y == 0) return x;
    r1 = x;
    r2 = y;
    while(r2!=0){
        q = r1 / r2; //quotient
        r = r1 % r2; //remainder
        r1 = r2;
        r2 = r;
    }
    return r1;
}

No comments:

Post a Comment