# 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 ## 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. Recently I started submitting code in Python and there was ## 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 of an array element. That is if the array length ## Fibonacci Series: Problem approach, fix Integer overflow and reduce time complexityFibonacci Series: Problem approach, fix Integer overflow and reduce time complexity

If you have ever done programming and went through some problems which need to be solved, you must have known the name of Fibonacci series. In the very first approach