VB.NET: Finding Common Multiple and Highest Common Factor (LCM-HCF)
Overview
When performing simple arithmetic with mixed fractions, finding the Lowest Common Multiple and Highest Common Factor enables simple calculations.
For example:
**25/120 + 32/72
= (25*3)/(120*3) + (32*5)/(72*5)
= 75/360 + 160/360
= 235/360
= (235/5)/(360/5)
**= **47/72
**
To do this both numbers must be factorized, to determine the common factors of the two numbers, the LCM of the two numbers, and the factor you must multiply both denominators and numerators by so both fractions have a common denominator.
The factorize Method
The factorize Method first determines the prime factors for both numbers entered, then compares those factors for common factors. The leftmost ListBox (labeled A.) contains the unique prime factors for the leftmost number. The rightmost ListBox (labeled C.) contains the unique prime factors for the rightmost number. Those factors that are present in both user entered numbers are listed in the middle Listbox.
The prime factors are determined by recursively compiling a list of all possible divisors of a number, starting with the initial user entered number, then repeating this operation with the penultimate number in the list as the new target on each iteration until the list only contains two numbers. The second number in the list, on each iteration is always a prime factor which also when multiplied by the list's penultimate number equals the target.
Private Sub factorize(ByVal numbers() As Integer, ByVal listBoxes() As ListBox, ByVal outputLabels() As Label)
If numbers.First > 9999999 OrElse numbers.Last > 9999999 Then
MsgBox("One or both numbers too large to factorise stably", MsgBoxStyle.Information)
Return
End If
For x As Integer = 0 To 1
Dim divisors As List(Of Integer) = getDivisors(numbers(x))
If divisors.Count <> 2 Then
Dim levels As New List(Of Point)
levels.Add(New Point(numbers(x), 1))
Do
divisors = getDivisors(levels.Last.X)
If divisors.Count > 2 Then
levels.Add(New Point(divisors(divisors.Count - 2), divisors(1)))
Else
Exit Do
End If
Loop
Dim factors As New List(Of Integer)
For Each p As Point In levels
If Not p.Y = 1 Then
factors.Add(p.Y)
End If
Next
factors.Add(levels.Last.X)
factors.Sort()
listBoxes(If(x = 0, 0, 2)).Items.Clear()
listBoxes(If(x = 0, 0, 2)).Items.AddRange(factors.Select(Function(i) i.ToString).ToArray)
Else
listBoxes(0).Items.Clear()
listBoxes(1).Items.Clear()
listBoxes(2).Items.Clear()
outputLabels(0).Text = "LCM ="
outputLabels(1).Text = "HCF = "
MsgBox(String.Format("{0} is a Prime Number", numbers(x)), MsgBoxStyle.Information)
Return
End If
Next
listBoxes(1).Items.Clear()
For x As Integer = listBoxes(0).Items.Count - 1 To 0 Step -1
Dim value As String = listBoxes(0).Items(x).ToString
Dim index As Integer = listBoxes(2).FindStringExact(value)
If index > -1 Then
listBoxes(1).Items.Add(value)
listBoxes(0).Items.RemoveAt(x)
listBoxes(2).Items.RemoveAt(index)
End If
Next
Dim dt As New DataTable
Dim productString1 As String = String.Join("*", listBoxes(0).Items.Cast(Of String).ToArray)
If listBoxes(1).Items.Count > 0 Then
Dim productString2 As String = String.Join("*", listBoxes(1).Items.Cast(Of String).ToArray)
productString1 &= If(listBoxes(0).Items.Count > 0, "*", "") & productString2
outputLabels(1).Text = String.Format("HCF ({0}) = {1}", productString2, dt.Compute(productString2, Nothing))
Else
outputLabels(1).Text = "HCF = "
End If
productString1 &= If(listBoxes(2).Items.Count > 0, "*", "") & String.Join("*", listBoxes(2).Items.Cast(Of String).ToArray)
outputLabels(0).Text = String.Format("LCM ({0}) = {1}", productString1, dt.Compute(productString1, Nothing))
End Sub
The getDivisors Function
The getDivisors Function returns a list of all possible divisor pairs sorted ASC
Private Function getDivisors(ByVal x As Integer) As List(Of Integer)
Return New List(Of Integer)(Enumerable.Range(1, x).Where(Function(n) x Mod n = 0).ToArray)
End Function
Other Resources