GCD greatest common divisor in C / C++

GCD Greatest Common Divisor in C  /  C++

So, let's first know what is GCD ?



GCD 


GCD of two or more integers, which are not all  " zero " ,  is the largest positive integer that divide each of the integers and the full form of GCD is GREATEST COMMON DIVISOR.
HCF  ( HIGHEST COMMON FACTOR ) and GCD  ( GREATEST COMMON DIVISOR ) both are same.





For example :- we have two numbers are 45 and 27 , so the GCD of 45 and 27 is 9 .

•  2nd Method

For example :- we have two numbers are 45 and 27 , so the GCD of 45 and 27 is 9 .


 n1   =   45 
 n2   =   27

so, first we calculate a        n1   -    n1     (   n1  subtract  n2    )   


  
45   -   27   =  18



and Now    n2    -    18  (  result  )  


27    -    18     =   9  



and Now    n2    -    9  (  result  )  


18    -   9     =     9  




and Now    n2    -    9  (  result  )  


9     -     9     =     9   



The answer is   :-     9










Program

Q)   WAP to calculate GCD of two numbers using while Loop


#include <iostream>
using namespace std;

int main()
{
    int n1, n2;

    cout << "Enter two numbers: ";
    cin >> n1 >> n2;
    
    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }

    cout << "HCF = " << n1;
    return 0;
}


Result






Enter two numbers: HCF = 9




In above program, smaller number is subtracted from larger number and that number is stored in place of larger number.

This process is continued until, two numbers become equal which will be HCF.




Have a Nice Stay Here   :- )