## Q. Write a program to find GCD of two numbers.

GCD :- 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 :-
Input = 20 and 15
Output = 5 is the GCD.
As we can see that 5 divides both 20 and 15 and we don't have any larger number that divides both the numbers therefore, the GCD of 20 and 15 is 5.

## GCD Algorithm

```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
```

# GCD Program

• C
• C++
• Java
• Python
• C#
• PHP
• ```#include <stdio.h>
int main()
{
int num1=60, num2=45, i, gcd;
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
gcd = i;
}
printf("GCD of %d and %d is %d", num1, num2, gcd);
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;
int main()
{
int num1=60, num2=45,i,gcd;
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
gcd = i;
}
cout << "GCD of "<< num1<<" and "<< num2<<" is "<< gcd;
return 0;
}
```
```public class LFC
{
public static void main(String args[])
{
int num1 = 60, num2 = 45;
int gcd;
for (int i = 1; i < num1 && i < num2; i++) {
if (num1 % i == 0 && num2 % i == 0)
gcd = i;
}
System.out.println("GCD of " + num1 +" and " + num2 + " is " + gcd);
}
}
```
```def find_gcd(num1, num2):
# choose the smaller number
if num1 > num2:
smaller = num2
else:
smaller = num1
for i in range(1, smaller+1):
if((num1 % i == 0) and (num2 % i == 0)):
gcd = i
return gcd
num1 = 60
num2 = 45
gcd=find_gcd(num1, num2)
print ("G.C.D. of ", num1, " and ", num2, " is ", gcd)
```
```using System;
class LFC {
// Recursive function to return
// gcd of num1 and num2
static int find_gcd(int num1, int num2)
{
// Everything divides 0
if (num1 == 0)
return num2;
if (num2 == 0)
return num1;
// base case
if (num1 == num2)
return num1;
// num1 is greater
if (num1 > num2)
return find_gcd(num1 - num2, num2);
return find_gcd(num1, num2 - num1);
}
// Driver method
public static void Main()
{
int num1 = 60, num2 = 45;
Console.WriteLine("GCD of "
+ num1 +" and " + num2 + " is "
+ find_gcd(num1, num2));
}
}
```
```function find_gcd(\$num1, \$num2)
{
// Everything divides 0
if (\$num1 == 0)
return \$num2;
if (\$num2 == 0)
return \$num1;
// base case
if(\$num1 == \$num2)
return \$num1 ;
// a is greater
if(\$num1 > \$num2)
return find_gcd( \$num1-\$num2 , \$num2 ) ;
return find_gcd( \$num1 , \$num2-\$num1 ) ;
}
// Driver code
\$num1 =  60;
\$num2 = 45;
echo "GCD of \$num1 and \$num2 is ", find_gcd(\$num1 , \$num2) ;
```
```#include <stdio.h>
int main()
{
int num1=60, num2=45, i, gcd;
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
gcd = i;
}
printf("GCD of %d and %d is %d", num1, num2, gcd);
return 0;
}```

#### Output

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

## Recommended Programs

Program to find LCM of 2 Numbers.
Program to find Perfect Number.