Fast Visual Basic Code to Find HCF (GCD)
This tutorial demonstrates an efficient Visual Basic method to calculate the Highest Common Factor (HCF),
also known as the Greatest Common Divisor (GCD). Using prime factorization and loop optimization,
students can learn how Visual Basic handles numerical sorting and divisor checks.
The H.C.F. code in VB.Net from the previous lesson could get a bit slow
if we run into a prime number and this prime number becomes the loop range.
Now functions come in handy, don't they?
Let's see how we can fix this and make a fast VB.Net algorithm to find HCF:
Step 1:
Do a numerical sort on the resulting set so its first member is the smallest in the set.
Step 2:
Find the factors of the first number in the set.
Step 3:
Iteratively check through the set of numbers with the factors from Step 2 to make sure it is common to all.
Step 4:
For each common factor, divide every member of the number set by the common factor.
Note: You can reuse the previous class and module if you want.
So! Visual Basic Fun Practice Exercise - Fast Find HCF
As a fun practice exercise, feel free to try out your own numbers, and see how the fast Visual Basic code finds the HCF of those numbers.
VB.Net Code for Fast HCF - Class File.
Dim set_of_numbers As New List(Of Integer) ' will hold the the values to be sent in
Dim arg_copy As New List(Of Integer)
Dim common_factors As New List(Of Integer) ' for housing all common factors
Dim minimal_prime_factors As New List(Of Integer)
Dim all_round_factor As Boolean
Dim calc_result As Integer
Dim index As Integer
' Simulate a constructor
Public Sub _init_(group As List(Of Integer))
For Each value In group
set_of_numbers.Add(value)
arg_copy.Add(value)
Next
' STEP 1:
set_of_numbers.Sort()
arg_copy.Sort()
index = 2
all_round_factor = False ' state flag
calc_result = 1
End Sub
' STEP 2:
' does the grunt work
' takes no arguments but requires 'set_of_numbers' to be set
Private Function findHCFFactors() As List(Of Integer)
Do While index < minimal_prime_factors.Count
all_round_factor = True
' STEP 3:
For count = 0 To set_of_numbers.Count - 1
If all_round_factor And arg_copy.Item(count) Mod minimal_prime_factors.Item(index) <> 0 Then
all_round_factor = False
End If
Next count
' STEP 4:
If all_round_factor Then
For count_off = 0 To set_of_numbers.Count - 1
arg_copy.Item(count_off) = CInt(arg_copy.Item(count_off) / minimal_prime_factors.Item(index))
Next count_off
common_factors.Add(minimal_prime_factors.Item(index))
End If
index += 1
Loop
Return Nothing
End Function
' Returns a scalar value Of the HCF
Public Function getHCF() As Integer
' use only direct factors Of the smallest member
Dim aux As New PrimeFactors
aux._init_(set_of_numbers.Item(0))
minimal_prime_factors = aux.onlyPrimeFactors()
' go ahead And see which of the above factors are mutual
index = 0
findHCFFactors()
'iterate through And retrieve members
For Each factor In common_factors
calc_result *= factor
Next
Return calc_result
End Function
End Class
VB.Net Code for Fast HCF - Main Module.
Sub Main()
' Use the fast HCF Class
Dim group As New List(Of Integer)({20, 30, 40})
Dim h_c_f As New FastHCF
h_c_f._init_(group)
Dim answer = h_c_f.getHCF()
Console.Write("The H.C.F. of " & String.Join(", ", group) & " is " & answer)
End Sub
End Module