Ankit Algorithms,Competitive Programming Program to find GCD of a number and optimize solution using Euclidean method

# Program to find GCD of a number and optimize solution using Euclidean method Finding greatest common divisor of a number is a very common mathematics problem and has a lot of implementation in computer science like cryptography, data security and other fields. By definition GCD of two numbers is the largest number which can divide both numbers.

So, we can derive a naive algorithm based on the definition:

```class GCD{
public static void main(String args[]){
System.out.println(gcd(10,20));
}
static int gcd(int a, int b){
int min=a;
if(b<a){
min=b;
}
for(int i=min;i>1;i--){
if(a%i ==0 && b%i==0)
return i;
}
return 1;
}
}
```

For large numbers which have very small GCD this algorithm go very very slow and test each and every number till GCD found. In such case to optimize the solution another approach of Euclidean method can be followed. According to this approach:

if a and b are two numbers for which we need to find GCD:

1. Divide the bigger number from the smaller number
2. Check if the remainder is 0 then the smaller number is the GCD
3. if remainder is not 0 then divide smaller number from remainder and check step 2 again.

With above approach we can easily reduce the steps to find the GCD of two numbers.

```class GCD{
public static void main(String args[]){
System.out.println(gcd(10,20));
}
static int gcd(int a, int b){
int remainder = -1;
int min=a;
int max=b;
if(b<a){
min=b;
max=a;
}
remainder = max%min;
if (remainder == 0)
return min;
else
return gcd(min, remainder);
}
}
```

Converting the algorithm to work for big integer we can do following:

```import java.math.BigInteger;
class GCD{
public static void main(String args[]){
System.out.println(gcd(new BigInteger("15"),new BigInteger("20")));
}
static BigInteger gcd(BigInteger a, BigInteger b){
BigInteger remainder = new BigInteger("-1");
BigInteger min=a;
BigInteger max=b;
if(b.compareTo(a)<0){
min=b;
max=a;
}
remainder = max.mod(min);
if (remainder.compareTo(new BigInteger("0")) == 0)
return min;
else
return gcd(min, remainder);
}
}
```

### Related Post ## Generate Combination SequenceGenerate Combination Sequence

Recently during a “Hiring Hackathon” of a company I went through a problem which required, to get all the combination ## N Queens Problem – Iterative to recursive derivationN Queens Problem – Iterative to recursive derivation

There is a problem named N Queens which is famous in computer science courses and some programming challenges. Most of ## Runtime Error in onlinejudge.org website for Java submissionRuntime Error in onlinejudge.org website for Java submission

I am using OnlineJudge.org website for years now but I used to submit my solutions in C++ and ANSI C.