Finding the GCD and LCM (the Euclidean algorithm)

This lesson covers the Euclidean algorithm in VB.NET, with the aim of understanding a mathematical algorithm built on recursion.

The Euclidean algorithm is the classic, efficient way of finding the greatest common divisor of two numbers. It works recursively on the property that the GCD of the larger and the remainder equals the GCD of the original pair.

In the sample code, GcdFunc() calls itself as GcdFunc(b, a Mod b) until b = 0. The least common multiple follows from "the product of the two divided by the GCD", which LcmFunc() uses.

A common early stumble is not knowing that relationship and trying to calculate the LCM from scratch with different logic. Once you have the GCD, one multiplication and one division give you the LCM.

In professional work, the thinking behind this algorithm is applied to mathematical work such as reducing fractions and calculating when processes with different periods coincide.

📖 Reference code

Function GcdFunc(a As Integer, b As Integer) As Integer
    If b = 0 Then Return a
    Return GcdFunc(b, a Mod b)
End Function

Function LcmFunc(a As Integer, b As Integer) As Integer
    Return (a * b) \ GcdFunc(a, b)
End Function

Console.WriteLine("GCD: " & GcdFunc(12, 18))
Console.WriteLine("LCM: " & LcmFunc(4, 6))

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run VB.NET directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).