Robson » Code » VB6 » Prime Factor Finder

 
' Prime Factor Finder v1.0


' Speed tests
' 1 to 100,000 = 0.71 seconds
' 1 to 250,000 = 2.25 seconds
' 1 to 500,000 = 5.42 seconds
' 1 to 1,000,000 = 13.91 seconds

' all variables are declared
Option Explicit

' this code shows example uses
Public Sub Main()

' display the prime factors of a random number
' in the format of a * a * a * a = b
' for example, 2 * 5 * 11 * 719 = 79090
Dim lngResult As Long
Randomize
lngResult = Int(100000 * Rnd) + 1
MsgBox Replace(PrimeFactors(lngResult), " ", " * ") & " = " & lngResult

' create a string array from the prime factors of a number
Dim strPrimeFactorsArray() As String
strPrimeFactorsArray = Split(PrimeFactors(70555))

' create a long array from the prime factors of a number
' prime factors of the example number are 5, 103 and 137
' so the array is {5,103,107}
Dim lngPrimeFactorsArray() As Long
Dim strPrimeFactors As String
strPrimeFactors = PrimeFactors(70555)
ReDim lngPrimeFactorsArray(UBound(Split(strPrimeFactors)))
Dim A As Integer
For A = 0 To UBound(Split(strPrimeFactors))
lngPrimeFactorsArray(A) = Split(strPrimeFactors)(A)
Next

End Sub

' returns the prime factors of a specified number
Public Function PrimeFactors(ByVal dblNumber As Double) As String
If dblNumber > 3 Then
' everything divides by 1, so it gets skipped
Dim dblDivisor As Long
dblDivisor = 2
Do
' this would usually be done with mod, but this method can handle bigger numbers
' returns true if the starting number divides by the loop counter exactly
If dblNumber / dblDivisor = dblNumber \ dblDivisor Then
' divide the starting number by this divisor
dblNumber = dblNumber / dblDivisor
' add to the factors string
PrimeFactors = PrimeFactors & dblDivisor & " "
Else
' checks are done on two and then every odd number after that.
' this is somewhat inefficient, but working out what is prime and what
' isn't would take longer
If dblDivisor = 2 Then
dblDivisor = dblDivisor + 1
Else
dblDivisor = dblDivisor + 2
End If
End If
' exit if a divisor was found or if it's so high that another can't be found
Loop Until dblDivisor * dblDivisor > dblNumber
End If
' return the prime factors
PrimeFactors = PrimeFactors & dblNumber
End Function

 
© 2004-17 robson | cc unless stated