calculate the GCD | Euclids Algorithm | c and cpp programming language

The G.C.D. ( Greatest Common Divisor ) or H.C.F. ( Highest Common Factor ) of two numbers is the largest positive integer that perfectly divides the two given numbers.

gcd(m,n) is degined as the most common divisor of two nonnegative, not-both-zero integers m and n that divides both evenly.

One of Euclid's volumes, most famous for its systematic presentation of geometry, outlines and algorithm for solving this problem.  Modern terms, Euclid's Algorithm includes applying equality repeatedly.

gcd(m,n) = gcd(n, m mod n)

Euclid's algorithm for computing gcd(m, n)

1. If n == 0, return the value of m as the answer and stop; otherwise proceed to Step 2.
2. Divide m by n and assign the value of the remainder to rem.
3. Assign the value of n to m and the value of rem to n. Go to Step 1.

We can express the same algorithm in a pseudocode (Euclid's Pseudocode)

//Computes gcd(m,n) by Euclid's Algorithm

// Input: Two non-negative, non-both-zer intergers m and n.

//Output: Greatest common Divisor of m and n.

while n == 0 do
    rem <- m mod n
    m <- n
    n <- r
return m

GCD by Euclid's Algorithm c program

#include <stdio.h>
// Define the function to calculate the GCD
int gcd(int m, int n){
    if(n == 0){
        return m; // if n == 0 then return the value of m
    }
    return gcd(n, m % n);
}

int main()
{
    int m, n;
    printf("Enter the first number : ");
    scanf("%d", &m);
    printf("Enter the second number : ");
    scanf("%d", &n);
    int GCD;
// Check the greater value of the give number by user.
    if(m < n){
        GCD = gcd(n, m);
    }else{
        GCD = gcd(m, n);
    }
    printf("GCD is : %d", GCD); // print the value of final GCD after calculation of two number
    return 0;
}

GCD by Euclid's Algorithm c++ program

#include <iostream>
using namespace std;

int gcd(int m, int n){
    if(n == 0){
        return m;
    }
    return gcd(n, m % n);
}

int main()
{
    int m, n;
    cout<<"Enter the first number : ";
    cin>>m;
    cout<<"Enter the second number : ";
    cin>>n;
    int GCD;
    if(m < n){
        GCD = gcd(n, m);
    }else{
        GCD = gcd(m, n);
    }
    cout<<"GCD is : "<< GCD;
    return 0;
}

Method 2

Consecutive integer checking algorithm for computing gcd(m,n)

1. Assign the value of min(m,n) to t.
2. Divide m by t. if the remainder of this division is 0, go to Step 3; otherwise, go to Step 4.
3. Divide n by t. If the remainder of this division is 0, return the value of  t as the answer and stop; otherwise, proceed to Step 4.
4. Decrease the value of t by 1. Go to Step 2.

Calculate GCD C program

#include<stdio.h>

int gcd(int m, int n){
    if(n == 0){
        return m;
    }
    int isFind = 0;
    int gcD;
    int t = n;
    while(isFind == 0){
        if(m % t == 0){
            gcD = t;
            if(n % gcD == 0){
                isFind = 1;
            }
        }
        t--;
    }
    return gcD;
}

int main(){
    int m = 60;
    int n = 24;
    int gcdAns = gcd(m, n);
    printf("GCD is : %d", gcdAns);
    return 0;
}

Calculate GCD C++ program

#include<iostream>
using namespace std;

int gcd(int m, int n){
    if(n == 0){
        return m;
    }
    int isFind = 0;
    int gcD;
    int t = n;
    while(isFind == 0){
        if(m % t == 0){
            gcD = t;
            if(n % gcD == 0){
                isFind = 1;
            }
        }
        t--;
    }
    return gcD;
}

int main(){
    int m = 60;
    int n = 24;
    int gcdAns = gcd(m, n);
    cout<<"GCD is : "<<gcdAns;
    return 0;
}

Method 3

GCD Calculate by the prime factors of the number.

1. Find the priime factors of m.
2. Find the prime factors of n.
3. Identify all the common factors in the two prime expansions found in Step 1 and Step 2. (If p is a common factor occuring p_m and p_n times in m and n, respectively, it should be repeated min(p_m, p_n) times.)
4. Compute the product of all the common factors and return in as the greatest commong divisior of the numbers given.

Thus, for the number 60 and 24, we get

60 = 2, 2, 3, 5

24 = 2, 2, 2, 3

gcd(60, 24) = 2, 2, 3, = 12

Calculate GCD C Program

#include<stdio.h>

int main(){
int m, n, gcd, i;
printf("Enter the first number : ");
scanf("%d", &m);
printf("Enter the second number : ");
scanf("%d", &n);
for(i=1; i <= m && i <= n; ++i)
{
    if(m%i==0 && n%i==0)
        gcd = i;
}

printf("GCD : %d", gcd);
return 0;
}

Calcualte GCD C++ Program

#include<iostream>
using namespace std;

int main(){
int m, n, gcd, i;
cout<<"Enter the first number : ";
cin>>m;
cout<<"Enter the second number : ";
cin>>n;
for(i=1; i <= m && i <= n; ++i)
{
    if(m%i==0 && n%i==0)
        gcd = i;
}

cout<<"GCD : "<<gcd;
return 0;
}

Comment...