## Q. C# Program to Find Gcd of Two Numbers.

Here you will find an algorithm and program in C# programming language to find GCD of two numbers. First let us understand what is GCD.

Explanation : GCD stands for Greatest Common Divisor, GCD of two numbers is the largest number that can exactly divide both numbers. It is also called as HCF.

For Example : GCD of 60 and 45 is 15. 15 is the greatest number which can divide both 60 and 45. Therefore GCD of 60 and 45 is 15.

## Algorithm to find GCD of two numbers

```START
1. Input 2 Numbers A and B and declare variable GCD which holds the result.
2. Run Loop i from 1 to i <= A and i <=B
Check if A & B are completely divisible by i or not if yes then
Assign GCD = i
Loop End
3. Output GCD
STOP
```

# C# Program to Find Gcd of Two Numbers

```using System;
class LFC {
static int find_gcd(int num1, int num2)
{
if (num1 == 0)
return num2;
if (num2 == 0)
return num1;
if (num1 == num2)
return num1;
if (num1 > num2)
return find_gcd(num1 - num2, num2);
return find_gcd(num1, num2 - num1);
}

public static void Main()
{
int num1 = 60, num2 = 45;
Console.WriteLine("GCD of "
+ num1 +" and " + num2 + " is "
+ find_gcd(num1, num2));
}
}
```

#### Output

```GCD of 60 and 45 is 15
```