Formula to Find GCD

GCD ( a, b ) = [ |a.b| ] / [ lcm(a, b) ]
HCF of factors = Product of the Numbers/ LCM of numbers

Examples:

Input: a = 20, b = 25
Output: 4

Input: a = 40, b = 50
Output: 10

Explanation: The factors of 20 are 1, 2, 4, 5, 10 and 20. The factors of 25 are 1, 5, and 25. Among these factors, 1 and 5 are the common factors of both 20 and 25. The greatest among the common factors is 5.

There are two methods to find the GCD or HCF of two numbers, these are:

• Using for loop
• Using the Recursion

We will explore all the above methods along with their basic implementation with the help of examples.

Given two numbers, the task is to find the GCD or HCF of two numbers in PHP. GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest positive integer that divides both numbers without leaving a remainder.