# GCD or HCF of two Numbers

Sun Feb 06 2022 03:26:58 GMT+0000 (Coordinated Universal Time)

```// Optimised Euclidean Algorithm Code : Time Complexity : O(log(min(a,b)))

import java.io.*;
import java.util.*;

public class Main {

static int gcd(int a, int b)
{
if(b==0)
return a;

return gcd(b, a % b);
}

public static void main (String[] args) {

int a = 12, b = 15;

System.out.println(gcd(a, b));

}
}

// Euclidean Algorithm Code

static int gcd(int a, int b)
{
while(a!=b)
{
if(a > b)
a = a - b;
else
b = b - a;
}

return a;
}

// Naive Method : Time Complexity : O(min(a,b))

static int gcd(int a, int b)
{
int res = Math.min(a,b);

while(res > 0)
{
if(a%res == 0 && b%res == 0)
{
break;
}
res--;
}

return res;
}```
content_copyCOPY

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them. 36 = 2 * 2 * 3 * 3 60 = 2 * 2 * 3 * 5 GCD = 2 * 2 * 3 = 12 A SIMPLE SOLUTION is to find all prime factors of both numbers, then find intersection of all factors present in both numbers. Finally, return product of elements in the intersection. a=10, b=15 res=10 res=9 res=8 res=7 res=6 res=5 An EFFICIENT SOLUTION is to use Euclidean algorithm which is the main algorithm used for this purpose. The idea is, GCD of two numbers doesn’t change if smaller number is subtracted from a bigger number. a=12, b=15 a=12, b=3 a=9, b=3 a=6, b=3 a=3, b=3 Basic Euclidean Algorithm for GCD The algorithm is based on the below facts. If we subtract a smaller number from a larger (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD. OPTIMISED EUCLIDEAN Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0. a%b : if a<b then a%b = a gcd(12,15) -> gcd(15,12) -> gcd(12,3) -> gcd(3,0)