Factorizing Numbers

[jemidiah]

The naive algorithm is to try dividing the number by larger and larger numbers until you get down to the number 1. In bad VB6 code that's nonetheless illustrative...

Private Sub Form_Load()
    Call GetFactors(60)
End Sub

Private Sub GetFactors(x As Long)
    If x <= 1 Then MsgBox "Bad x"

    div = 2
    Do Until x = 1
        If x Mod div = 0 Then
            MsgBox div & " is a factor"
            x = x / div
        Else
            div = div + 1
        End If
    Loop
    MsgBox "Factors complete."
End Sub

In words, using the example given, the routine tries dividing 60 by 2. If the remainder, which is returned by "60 mod 2", is zero, 2 is a factor. We divide off that factor and continue the loop. 30 is also divisible by 2, giving another factor of 2 and resetting x to 15. However, 15 is not divisible by 2 (15 mod 2 = 1, since 15/2 has a remainder of 1). So, we try the next number, 3. 15 is divisible by 3, so we divide off the 3 to get 5 and continue the loop to check if 5 is divisible by 3. Note that 5 can't be divisible by 2 since 15=3*5 wasn't divisible by 2. Since 5 is prime, it won't be divisible by anything except itself, resulting in a few more runs through the loop while div increments from 3 to 4 and finally to 5. Dividing off the 5, we get 1, which signals that we're done.

There are many optimizations to this strategy which become horrifically complicated. Also, if you're using large numbers, you'd need some form of BigInt's, since Longs will (relatively quickly) not provide enough precision to store large integers.