PowerShell Script to Find LCM of Two Numbers

Use the formula LCM(a,b) = (a * b) / GCD(a,b) in PowerShell by first finding the GCD with a function, then calculating LCM with function Get-LCM($a, $b) { $gcd = Get-GCD $a $b; return ($a * $b) / $gcd }.

Examples

Inputa=4, b=6

Output12

Inputa=21, b=6

Output42

Inputa=13, b=17

Output221

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (GCD). Then use the formula LCM = (a * b) / GCD. This works because the product of two numbers equals the product of their GCD and LCM.

Algorithm

1

Get two numbers as input.

2

Calculate the GCD of the two numbers using the Euclidean algorithm.

3

Calculate LCM by dividing the product of the two numbers by their GCD.

4

Return the LCM.

Code

powershell

function Get-GCD($a, $b) {
    while ($b -ne 0) {
        $temp = $b
        $b = $a % $b
        $a = $temp
    }
    return $a
}

function Get-LCM($a, $b) {
    $gcd = Get-GCD $a $b
    return ($a * $b) / $gcd
}

# Example usage
$a = 12
$b = 18
$lcm = Get-LCM $a $b
Write-Output "LCM of $a and $b is $lcm"

Output

LCM of 12 and 18 is 36

Dry Run

Let's trace LCM calculation for a=12 and b=18 through the code

1

Calculate GCD

Start with a=12, b=18; 18 != 0, temp=18, b=12 % 18=12, a=18

2

Continue GCD loop

a=18, b=12; 12 != 0, temp=12, b=18 % 12=6, a=12

3

Continue GCD loop

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

4

GCD found

b=0, exit loop, GCD=6

5

Calculate LCM

LCM = (12 * 18) / 6 = 216 / 6 = 36

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

Why This Works

Step 1: Why find GCD first?

The GCD helps find the largest number dividing both inputs, which is key to calculating the LCM efficiently.

Step 2: Using the formula

The formula LCM = (a * b) / GCD works because the product of two numbers equals the product of their GCD and LCM.

Step 3: Euclidean algorithm for GCD

The Euclidean algorithm repeatedly replaces the larger number by the remainder until zero, efficiently finding the GCD.

Alternative Approaches

Brute force search

powershell

function Get-LCM-BruteForce($a, $b) {
    $max = [Math]::Max($a, $b)
    $lcm = $max
    while (($lcm % $a -ne 0) -or ($lcm % $b -ne 0)) {
        $lcm++
    }
    return $lcm
}

Write-Output (Get-LCM-BruteForce 12 18)

Simple but slow for large numbers because it checks multiples one by one.

Using .NET built-in GCD

powershell

Add-Type -AssemblyName System.Numerics
function Get-LCM-DotNet($a, $b) {
    $gcd = [System.Numerics.BigInteger]::GreatestCommonDivisor($a, $b)
    return ($a * $b) / $gcd
}
Write-Output (Get-LCM-DotNet 12 18)

Uses .NET library for GCD, cleaner but requires .NET support.

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

Time Complexity

The Euclidean algorithm for GCD runs in O(log(min(a,b))) time, which dominates the calculation. Multiplication and division are constant time.

Space Complexity

The algorithm uses a fixed number of variables, so space complexity is O(1).

Which Approach is Fastest?

Using the Euclidean algorithm for GCD is fastest. Brute force is slow for large inputs. Using .NET built-in GCD is clean and efficient if available.

Approach	Time	Space	Best For
Euclidean Algorithm	O(log(min(a,b)))	O(1)	All input sizes, efficient
Brute Force Search	O(a*b)	O(1)	Small numbers, simple code
.NET Built-in GCD	O(log(min(a,b)))	O(1)	When .NET libraries are available