Euclid’s Algorithm

Euclid’s Algorithm

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

Step 1 If n = 0, return the value of m as the answer and stop; 

otherwise, proceed to Step 2.

Step 2 Divide m by n and assign the value of the remainder to r.

Step 3 Assign the value of n to m and the value of r to n.

 Go to Step 1.

ALGORITHM Euclid(m, n)

//Computes gcd(m, n) by Euclid’s algorithm

//Input: Two non-negative, not-both-zero integers m and n

//Output: Greatest common divisor of m and n

while n = 0 do

r ← m mod n

m ← n

n ← r

return m

C program:

// C program to demonstrate Basic Euclidean Algorithm

#include <stdio.h>

// Function to return gcd of a and b

int gcd(int a,int b)

{

int n=b;

int rem,m=a;

    while(n!=0)

    {

        rem=m%n;

        m=n;

        n=rem;

    }

    return m;

}

int main()

{

    int a,b;

    printf("Enter two elements to find GCD");

    scanf("%d %d",&a,&b);

    printf("GCD(%d, %d) = %d",a,b, gcd(a, b));

    return 0;

}

Output:

Enter two elements to find GCD 5

13

GCD(5, 13) = 1

Other Method-:

int gcd(int a, int b)

{

    if (a == 0)return b;

    return gcd(b%a, a);

}