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

Here you will find an algorithm and program in PHP 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
```

# PHP Program to Find Gcd of Two Numbers

```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 ) ;
}

\$num1 =  60;
\$num2 = 45;
echo "GCD of \$num1 and \$num2 is ", find_gcd(\$num1 , \$num2) ;
```

#### Output

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