GCD and HCF

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them.

For example GCD of 20 and 28 is 4 and GCD of 98 and 56 is 14.

/*Code 1:
An **efficient solution  is to use [Euclidean algorithm ]
which is the main algorithm used for this purpose. The idea is, 
GCD of two numbers doesn’t change if smaller number is subtracted from a bigger number.*/

//c program to find GCD and HCF of two numbers
#include <iostream>
using namespace std;

//Recursive function to return gcd and hcf a and b
int gcd(int a,int b)
{
    //Everything divides 0
    if(a == 0 || b == 0)
        return 0;
    //base case 
    if(a == b)
        return a;
    //a is greater  
    if(a > b)
        return gcd(a-b,b);
    return gcd(a,b-a);
    
}
//Driver program to test above functon
int main()
{
    int a,b,m,n;
    cin >> a >> b;//input a and b
    m = a, n = b;//use two variabes a and b to keep a and b
    int com = gcd(a,b);//get GCD and keep it
    int result = m * n / com;//calculate the HCF and keep it 
    printf("Greatest Common Divisor is %d\n",com);
    printf("Highest Common Factor is %d\n",result);
    
    return 0;
} 

/*Code 2:
A more efficient solution **is to use modulo operator in [Euclidean algorithm ]*/
//C program to find GCD and HCF of two numbers
#include <iostream>
using namespace std;

//Recursize function to return gcd of a and b
int gcd(int a,int b)
{
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
//Driver program to test above function
int main()
{
    int a,b,m,n;
    cin >> a >> b;
    m = a,n = b;
    
    int com = gcd(a,b);//get the GCD and keep it 
    int result = m * n / com;//calculate HCF and keep it
    printf("Greatest Common Divisor is %d\n",com);
    printf("Highest Common Factor is %d\n",result);
    return 0;
} 

//Code 3: using circles to solve the question about GCD and HCF
#include <iostream>
using namespace std;
const int ERROR = -1;

int gcd(int a,int b)//a function to get GCD
{
    if(a == 0 || b == 0)//judge if variabe a or b is equal to 0 or not ,if it is, exist the function
        return ERROR;
    int i;
    int min = (a < b) ? a:b;//find out the minimum one of the two numbers
    
    for(i = min; i >= 1; i--)//circle and find out  GCD
    {
        if(a % i == 0 && b % i == 0)    
            break;
    }
    return i; //i is the GCD
}

int hcf(int a,int b)//a function to get HCF
{
    if(a == 0 || b == 0)//judge if variabe a or b is equal to 0 or not ,if it is, exist the function
        return ERROR;
    int i;
    int max = (a > b) ? a:b;//get the Maximum number of the two numbers
    for(i = max;; i++)
    {
        if(i % a == 0 && i % b == 0)
            break;
    }
    return i;   //i is the HCF
}

int main()
{
    int a,b;
    
    cin >> a >> b;  //input two nubers

    int com = gcd(a,b);//get GCD and keep it by variable com
    if(com == ERROR)
    {
        printf("ERROR\n");
    }
    else
    {
        printf("%d\n",com);
    }
    int res = hcf(a,b);//get HCF and store it with the variabe res  
    
    if(res == ERROR)
    {
        printf("ERROR\n");
    }
    else
    {
        printf("%d\n",res); 
    }

    return 0;
} 

//test input:
98 56
Greatest Common Divisor is 14
Highest Common Factor is 392

Attention：In the test case, regarding 0, you need to pay special attention,because any integer cannot get 0 from its factor, so 0 cannot be combined with any integer to find the GCD or the HCF.

---

You can leave me a message if you find out any mistake in my diary, I'll correct it, thanks.