' 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