You're online now.

Hurray! you are online now.

Calculate the GCD | Euclidean algorithm | c and cpp programming language

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

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

One of Euclidean volumes, most famous for its systematic presentation of geometry, outlines and algorithm for solving the problem of gcd. Modern terms, Euclidean algorithm includes applying equality repeatedly.

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

Euclidean algorigthm for computing gcd(m, n)

  1. If n == 0, return the value of m as the answer and stop; other 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 (Euclidean Pseudocode)

// computes gcd(m, n) by Euclidean algorithm
    // Input: Two non-negative, not-both-zero integers m and n.
    // Output: Gretaest common divisor of m and n.
    while n == 0 do
        rem <- m mod n
        m <- n
        n <- r
    return m

GCD by Euclidean Algrorithm c prgrogram

#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 Euclidean Algrotithm 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 to calculate the GCD

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.
  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 to calculate the GCD

GCD calculate by the prime factors of the number.

  1. Find the prime 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 pm and pn times in m and n, respectively, it should be repeated min(pm, pn) times.
  4. Compute the product of all the commong factors and return in as the greatest common divisor of the numbers given.

For Example: 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 = (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;
    }

Calculate 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;
    }
🖤 0
Buy me coffee ☕

Comments

Oops!

No comments here...