Factorizing Numbers

[storm5510]

I've searched the web over and not found anything I can understand or implement. So, what I am looking for is a way to factor a number into its separate parts, like so:

60 = 2 x 2 x 3 x 5

I understand the process, but coding it gives me fits. Yes, I looked in the code banks here too.

Anyone?

[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.

[storm5510]

I've seen references to "BigInt" on a few web sites. Not sure what platform uses it? I used "Double" instead even though I didn't need the decimal places; probably takes more time to deal with it.

[jemidiah]

"Double" is probably not the best idea since the mod function requires integers (numbers without decimals). Whenever you check divisibility, it's got to convert from Double to Long, making your routine all the slower. Then again, it doesn't seem like that's a big problem with your application.

BigInts are available in (at the least) Java and Python. The name might be slightly different depending on the language. The basic idea is this: try to store the number 12345678901234567890123456789 in VB6. If you use a Long, you'll get an Overflow error. If you use a Single or Double, the system will automatically round off after some point. For instance, a Single in VB6 trying to store the above actually stores 12345680000000000000000000000000000. To compute prime factorizations, you need all of the digits. How can you store such large numbers? The answer is in a special class, often named BigInt. You can store arbitrarily large numbers in BigInts (so long as they don't have a decimal part). It's very convenient for certain applications to be able to do so. For instance, if you were trying to find the prime factorization of 1267650600228229401496703205376 [= 2^100] you'd need BigInts to use the algorithm I posted above.