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);
}
