# Finding Lowest Common Multiple and Highest Common Factor (LCM-HCF)

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

LCM = 360... so...

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.

You'll notice the two inactive tabs showing 120 and 72. These display Prime Factor Trees.

## The getLists and getPrimeFactors Functions

The getLists Function returns an array of List(of Integer). The first and last Lists are the prime factors of the numbers (in this case) 120 and 72. The Function then separates the common factors from the first two lists. The GUI ListBoxes (from left to right) use Lists 0 to 2 as their datasource. At this point, the setOutput Function is called in the GUI to calculate the itemised LCM and HCF which is displayed below the ListBoxes. A helper Function (getProduct) is used in the calculations.

## The getLists Function

```Public Shared Function getLists(ByVal x As Integer, ByVal y As Integer) As List(Of Integer)()
Dim lists(2) As List(Of Integer)

lists(0) = If(x > 0, getPrimeFactors(x), New List(Of Integer))
lists(2) = If(y > 0, getPrimeFactors(y), New List(Of Integer))

lists(1) = New List(Of Integer)

If lists(0).Count > 0 AndAlso lists(2).Count > 0 Then
For i As Integer = lists(0).Count - 1 To 0 Step -1
If lists(2).Contains(lists(0)(i)) Then
lists(0).Remove(lists(1).Last)
lists(2).Remove(lists(1).Last)
End If
Next
End If

Return lists

End Function
```

## The getPrimeFactors Function

The Factors are calculated by dividing n (the target) by an increasingly growing factor (comprised of 2, then 3, then every odd number thereafter), which filters out the Prime Factors.

```' Return the number's prime factors.
Private Shared Function getPrimeFactors(ByVal n As Integer) As List(Of Integer)
Dim result As New List(Of Integer)

' Take out the 2s.
Do While n Mod 2 = 0
n \= 2
Loop

' Take out other primes.
Dim factor As Integer = 3
Do While factor * factor <= n
If n Mod factor = 0 Then
' This is a factor.
n \= factor
Else
' Go to the next odd number.
factor += 2
End If
Loop

' If num is not 1, then whatever is left is prime.
If n > 1 Then
End If

Return result
End Function
```

## The getProduct Function

This is a helper Function that calculates the product of one or more List(of Integer)

```Public Shared Function getProduct(ByVal ParamArray lists As List(Of Integer)()) As Integer
If lists.All(Function(l) l.Count = 0) Then Return 0
Dim p As Integer = -1
For x As Integer = 0 To lists.Count - 1
For y As Integer = 0 To lists(x).Count - 1
If lists(x)(y) > 0 AndAlso p = -1 Then
p = lists(x)(y)
Else
p *= lists(x)(y)
End If
Next
Next

Return p

End Function
```

## The getTree (graphics) Function

The Prime Factor Trees, shown on the second and third TabPages, display dynamic images, created for each newly entered number on the fly.

```Public Shared Function getTree(ByVal n As Integer) As Bitmap
Dim levels As New List(Of Point)
Dim f As New Font("Calibri", 14, FontStyle.Regular, GraphicsUnit.Pixel)
Dim label As String
'******************************************************************************************************
Dim img As New Bitmap(490, 465)
Dim gr As Graphics = Graphics.FromImage(img)
gr.Clear(Color.White)

Dim sf As New StringFormat
sf.Alignment = StringAlignment.Center
sf.LineAlignment = StringAlignment.Center

'*******************************************************************************************************

If n > 9999999 Then
'*******************************************************************************************************
gr.DrawString("Number too large to factorise stably", f, Brushes.Black, New Rectangle(0, 0, 472, 30), sf)
Return img
'*******************************************************************************************************
End If
If n > 1 Then
Dim divisors As List(Of Integer) = coreFactors.getDivisors(n)
If divisors.Count > 2 Then
levels = New List(Of Point)
Do
divisors = coreFactors.getDivisors(levels.Last.X)
If divisors.Count > 2 Then
Else
Exit Do
End If
Loop
Dim indices As New Dictionary(Of Integer, Integer)
For Each p As Point In levels
If Not p.Y = 1 Then
If indices.ContainsKey(p.Y) Then
indices(p.Y) += 1
Else
End If
End If
Next
If indices.ContainsKey(levels.Last.X) Then
indices(levels.Last.X) += 1
Else
End If
label = String.Join(" * ", indices.Select(Function(kvp) If(kvp.Value > 1, String.Format("{0}^{1}", kvp.Key, kvp.Value), kvp.Key.ToString)).ToArray)
Else
gr.DrawString(String.Format("{0} is a Prime Number", n), f, Brushes.Black, New Rectangle(0, 0, 472, 30), sf)
Return img
End If
Else
gr.DrawString(String.Format("{0} is a Prime Number", n), f, Brushes.Black, New Rectangle(0, 0, 472, 30), sf)
Return img
End If
Dim textSize As SizeF = gr.MeasureString("1", f)
Dim newHeight As Integer
Dim newWidth As Integer
If levels.Count > 4 Then
newHeight = 12 + 54 + CInt((30 + textSize.Height) * levels.Count)
Else
newHeight = 262
End If
If levels.Count > 6 Then
newWidth = 75 + levels.Count * 40
Else
newWidth = 331
End If

'************************************************************************************************************
img = New Bitmap(1000, 1000)
gr = Graphics.FromImage(img)
gr.Clear(Color.White)

Dim pen As New Pen(Color.Black, 2)
Dim xPosition As Integer = img.Width - 75
Dim yPosition As Integer = 12
textSize = gr.MeasureString(levels(0).X.ToString, f)
gr.DrawString(levels(0).X.ToString, f, Brushes.Black, xPosition, yPosition)
For x As Integer = 1 To levels.Count - 1
Dim startPosition As New Point(xPosition + (CInt(textSize.Width) \ 2), yPosition + CInt(textSize.Height))
gr.DrawLine(pen, startPosition.X, startPosition.Y, startPosition.X + 30, startPosition.Y + 30)
textSize = gr.MeasureString(levels(x).Y.ToString, f)
gr.DrawString(levels(x).Y.ToString, f, Brushes.Red, startPosition.X + 30 - (CInt(textSize.Width) \ 2), startPosition.Y + 30)
gr.DrawLine(pen, startPosition.X, startPosition.Y, startPosition.X - 30, startPosition.Y + 30)
textSize = gr.MeasureString(levels(x).X.ToString, f)
gr.DrawString(levels(x).X.ToString, f, If(x = levels.Count - 1, Brushes.Red, Brushes.Black), startPosition.X - 30 - (CInt(textSize.Width) \ 2), startPosition.Y + 30)
xPosition = startPosition.X - 30 - CInt(textSize.Width)
yPosition = startPosition.Y + 30
Next

xPosition -= 20
yPosition += 30

Dim img2 As New Bitmap(1000 - xPosition, yPosition)
Dim gr2 As Graphics = Graphics.FromImage(img2)
gr2.DrawImage(img, 0, 0, New Rectangle(xPosition, 0, img2.Width, img2.Height), GraphicsUnit.Pixel)

img = New Bitmap(490, 465)
gr = Graphics.FromImage(img)
gr.Clear(Color.White)

Dim scaleX As Decimal = CDec(490 / img2.Width)
Dim scaleY As Decimal = CDec(465 / img2.Height)

If scaleX < 1 Then
If scaleX <= scaleY Then
img2 = New Bitmap(img2, CInt(img2.Width * scaleX), CInt(img2.Height * scaleX))
End If
End If
If scaleY < 1 Then
If scaleY < scaleX Then
img2 = New Bitmap(img2, CInt(img2.Width * scaleY), CInt(img2.Height * scaleY))
End If
End If

img = New Bitmap(490, 519)
gr = Graphics.FromImage(img)
gr.Clear(Color.White)

gr.DrawImage(img2, New Point(CInt((img.Width - img2.Width) / 2), CInt((465 - img2.Height) / 2)))
gr.DrawString(label, f, Brushes.Red, New Rectangle(0, 470, 490, 30), sf)

Return img

End Function
```

Used together, these tools can tell you everything you need to know about the Prime Factors of any number, in a couple of the more common ways used in mathematics.