PHP Program to Find HCF of Two Numbers

You can find the HCF of two numbers in PHP using the Euclidean algorithm with a loop like while($b != 0) { $temp = $b; $b = $a % $b; $a = $temp; } where $a ends as the HCF.

Examples

Input12, 18

Output6

Input100, 25

Output25

Input7, 13

Output1

How to Think About It

To find the HCF of two numbers, think about the largest number that divides both without leaving a remainder. The Euclidean algorithm helps by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the HCF.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero, do:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second number.

5

When the second number becomes zero, the first number is the HCF.

6

Return the first number as the HCF.

Code

php

<?php
function findHCF($a, $b) {
    while ($b != 0) {
        $temp = $b;
        $b = $a % $b;
        $a = $temp;
    }
    return $a;
}

$num1 = 12;
$num2 = 18;
echo "HCF of $num1 and $num2 is: " . findHCF($num1, $num2);
?>

Output

HCF of 12 and 18 is: 6

Dry Run

Let's trace the example with inputs 12 and 18 through the code.

1

Initial values

$a = 12, $b = 18

2

First loop iteration

temp = 18; $b = 12 % 18 = 12; $a = 18

3

Second loop iteration

temp = 12; $b = 18 % 12 = 6; $a = 12

4

Third loop iteration

temp = 6; $b = 12 % 6 = 0; $a = 6

5

Loop ends

$b is 0, so HCF is $a = 6

$a	$b	Operation
12	18	Start
18	12	$b = 12 (12 % 18)
12	6	$b = 6 (18 % 12)
6	0	$b = 0 (12 % 6)

Why This Works

Step 1: Using the Euclidean Algorithm

The code uses the Euclidean algorithm which finds the HCF by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller.

Step 2: Loop until remainder is zero

The loop continues until the remainder becomes zero, meaning the smaller number divides the larger exactly.

Step 3: Return the last non-zero remainder

When the remainder is zero, the last non-zero remainder stored in $a is the HCF.

Alternative Approaches

Recursive Euclidean Algorithm

php

<?php
function findHCFRecursive($a, $b) {
    if ($b == 0) {
        return $a;
    } else {
        return findHCFRecursive($b, $a % $b);
    }
}

$num1 = 12;
$num2 = 18;
echo "HCF of $num1 and $num2 is: " . findHCFRecursive($num1, $num2);
?>

This uses recursion instead of a loop, which can be cleaner but may use more stack memory for very large inputs.

Using Built-in PHP Function gcd (PHP 7.4+)

php

<?php
$num1 = 12;
$num2 = 18;
echo "HCF of $num1 and $num2 is: " . gmp_gcd($num1, $num2);
?>

This uses PHP's GMP extension function for gcd, which is very efficient but requires the GMP extension installed.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

The Euclidean algorithm runs in logarithmic time relative to the smaller input because each step reduces the problem size significantly.

Space Complexity

The algorithm uses constant extra space as it only stores a few variables and updates them in place.

Which Approach is Fastest?

The iterative Euclidean algorithm is fast and uses minimal memory; recursion is clean but uses stack space; built-in functions are fastest if available.

Approach	Time	Space	Best For
Iterative Euclidean Algorithm	O(log(min(a,b)))	O(1)	General use, efficient and simple
Recursive Euclidean Algorithm	O(log(min(a,b)))	O(log(min(a,b)))	Clean code, small inputs
Built-in GMP gcd Function	Highly optimized	O(1)	When GMP extension is available