Greatest common divisor

#1

Not getting logic of gcd

#2

hi @kumarakash121005
Euclidean algorithm

The algorithm is based on below facts.

  • If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change.
  • So if we keep subtracting repeatedly the larger of two, we end up with GCD.
  • Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

Code–>

#include<iostream>
using namespace std;

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

int main() {
    int n1,n2;
    cin>>n1>>n2;
    cout<<gcd(n1,n2)<<endl;
    return 0;
}