LCM-HCF



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(1).Add(lists(0)(i))
                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
        result.Add(2)
        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.
            result.Add(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
        result.Add(n)
    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)
            levels.Add(New Point(n, 1))
            Do
                divisors = coreFactors.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 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
                        indices.Add(p.Y, 1)
                    End If
                End If
            Next
            If indices.ContainsKey(levels.Last.X) Then
                indices(levels.Last.X) += 1
            Else
                indices.Add(levels.Last.X, 1)
            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.



Download here...



Try it now...