PowerShell Script to Find HCF of Two Numbers

Use the Euclidean algorithm in PowerShell with while ($b -ne 0) { $temp = $b; $b = $a % $b; $a = $temp } to find the HCF of two numbers stored in variables $a and $b.

Examples

Inputa=12, b=15

Output3

Inputa=100, b=25

Output25

Inputa=7, b=13

Output1

How to Think About It

To find the HCF of two numbers, repeatedly replace the larger number by the remainder when divided by the smaller number 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.

Code

powershell

$a = 48
$b = 18
while ($b -ne 0) {
    $temp = $b
    $b = $a % $b
    $a = $temp
}
Write-Output "HCF is $a"

Output

HCF is 6

Dry Run

Let's trace the example where a=48 and b=18 through the code

1

Initial values

a=48, b=18

2

First iteration

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

3

Second iteration

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

4

Third iteration

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

a	b	temp	b after modulo
48	18	18	12
18	12	12	6
12	6	6	0

Why This Works

Step 1: Why use the remainder

The remainder operation % helps reduce the problem size by replacing the larger number with the remainder when divided by the smaller number.

Step 2: Loop until remainder is zero

We keep updating the numbers until the remainder becomes zero, which means the last non-zero number is the HCF.

Step 3: Final result

When the loop ends, the variable $a holds the highest common factor of the original two numbers.

Alternative Approaches

Recursive function

powershell

function Get-HCF($a, $b) {
  if ($b -eq 0) { return $a }
  else { return Get-HCF $b ($a % $b) }
}
$a = 48
$b = 18
Write-Output "HCF is $(Get-HCF $a $b)"

Uses recursion for a cleaner approach but may be less intuitive for beginners.

Using built-in .NET method

powershell

$a = 48
$b = 18
Add-Type -AssemblyName System.Numerics
$hcf = [System.Numerics.BigInteger]::GreatestCommonDivisor($a, $b)
Write-Output "HCF is $hcf"

Leverages .NET library for simplicity but requires understanding of .NET interop.

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

Time Complexity

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

Space Complexity

The algorithm uses constant extra space, only a few variables to store numbers and temporary values.

Which Approach is Fastest?

The iterative Euclidean algorithm is generally fastest and simplest; recursion adds overhead, and using .NET methods adds dependency but can be convenient.

Approach	Time	Space	Best For
Iterative Euclidean	O(log(min(a,b)))	O(1)	Simple and efficient for all cases
Recursive Euclidean	O(log(min(a,b)))	O(log(min(a,b)))	Cleaner code but uses call stack
.NET Built-in	O(log(min(a,b)))	O(1)	Quick use if .NET knowledge is available