Greatest Common Divisor

Algorithm 1: Naive Algorithm

we are given two numbers a and b. a ≥ b

we take numbers from 1 to b including 1 and b and select biggest number that divides a and b.

Pseudo code :

    gcd(a, b):
        result = 1
        for i = 1 to b:
            if a%i ==0 and b%i == 0:
                  result = i
        return result      
    

Code :

    // finding gcd naive method
    // complexity O(n)
    #include <stdio.h>
    
    int gcd(int a, int b)
    {
        int res = 1;
        for (int i = 1; i <= b; i++)
        {
            if (a % i == 0 && b % i == 0)
            {
                res = i;
            }
        }
        return res;
    }
    
    int main()
    {
        int a, b;
        printf("Enter a: ");
        scanf("%d", &a);
        printf("Enter b: ");
        scanf("%d", &b);
    
        printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    }
    

Complexity Analysis :

we see that the algorithm has to go through b steps. Hence Time complexity is O(b).

Euclid's Algorithm for finding GCD

Here we take a and b and calculate the remainder a%b.

Taking b as a and this remainder a%b as b , we repeat the above and this step until b becomes 0 when we say a is the gcd.

Pseudo code :

    gcd (a, b) :
        if b == 0:
            return a
        else:
            return gcd(b, a%b)
    

Code :

    // Euclid's Algorithm for gcd
    #include <stdio.h>
    
    int gcd(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
    
        return gcd(b, a % b);
    }
    
    int main()
    {
        int a, b;
        printf("Enter a: ");
        scanf("%d", &a);
        printf("Enter b: ");
        scanf("%d", &b);
    
        printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    }
    

Complexity Analysis :

Time complexity is O(n) and this is the best known algorithm for finding gcd.