Finding factors of a number. Code crashes with big numbers

[korhan]

Hi,
Can anybody tell me why this code is crashing and also suggest a more efficient code maybe?

<code>
Function Factors(x As Double) As String
    Application.Volatile
    Dim i As Double
    Factors = x
    For i = x - 1 To 1 Step -1
        If x - (Int(x / i) * i) = 0 Then
            Factors = Factors & ", " & i
            Debug.Print Factors
        End If
    Next i
End Function


Sub Test()
    Call Factors(600851475143#)
End Sub
</code>

 

[footoo]

For the number you posted (600 trillion), if the code were able to loop at the rate of 60,000 per second, it would take about 115 days.

This link may help to get more efficient code:
Factors of a number (Excel) | Windows Secrets Lounge

 

[footoo]

Also, the Immediate window has a data limit - 199 lines, I think.

 

[thisoldman]

Here's my solution:

Function Factors(x As Double) As String
    Application.Volatile
    Dim i As Double
    Dim other_factors As String

    Factors = 1
    For i = 2 To Sqr(x)
        If x - Fix(x / i) * i = 0 Then
            Factors = Factors & ", " & i
            If i <> x / i Then
                other_factors = x / i & ", " & other_factors
            End If
            Debug.Print "Factors: " & Factors
            Debug.Print "other_factors: " & other_factors
            Debug.Print
        End If
    Next i
    
    If x <> 1 Then
        Factors = Factors & ", " & other_factors & x
    End If
    Debug.Print "Factors of " & x & " are:"
    Debug.Print Factors
End Function
''''

Sub Test()
    Call Factors(600851475143#)
End Sub
''''

 

[korhan]

thisoldman, how did you do it? Could you explain what your code is doing more efficiently? It is insanely quick.
Thanks for your help.

 

[korhan]

I guess the part i am trying to understand is

If i <> x / i Then
  other_factors = x / i & ", " & other_factors
End If

 

[thisoldman]

Thanks for the complement.

I can reconstruct the reasoning now that the code is written. Some of this logic wasn't new to me—I have written prime number tests in Python and Perl when dabbling into those languages.

Factors have to be symmetric: for every small factor of x, there is a corresponding large factor. If 2 is a factor of x, then x/2 is also a factor of x. If 3 is a factor, then x/3 is also a factor. So when you find one factor, you have also found its correspondent factor. We don't have to test every number, n, between 1 and x. We only have to test, maybe, half of them.

So, the count of factors below a certain point must be equal to the count of factors above that point. I had to ponder about locating the point of symmetry. After a few tests with pencil and paper, and the numbers 36 and 120, I convinced myself that the point of symmetry was the square root.

We only have to test for factors between 1 and Sqr(x) or between Sqr(x) and x. It shouldn't take too many example trials to convince yourself that the count of whole numbers between 1 and Sqr(x) is less than the count of whole numbers between Sqr(x) and x. So we will have to run fewer tests if we make our For loop run from 1 to Sqr(x) than if we test all the whole numbers between Sqr(x) and x.

Commented code, sans Debug.Prints.

Function Factors(x As Double) As String
    Application.Volatile
    Dim i As Double
    Dim other_factors As String

    ' 1 and x both have to be factors. Start our results collection with 1.
    Factors = 1
    
    ' Half of the factors will be below the square root of x.
    For i = 2 To Sqr(x)
    
        ' Same as x Mod i = 0 but works for large numbers. Int(x/i) works too.
        If x - Fix(x / i) * i = 0 Then
            
            ' Add the low value factor to the result string.
            Factors = Factors & ", " & i
            
            ' Don't add the square root to both strings.
            If i <> x / i Then
            
                ' Collect the corresponding large factors in a second string.
                other_factors = x / i & ", " & other_factors
            End If
        End If
    Next i
    
    ' If x is one, don't add it to the results again: the results string
    '   is already complete.
    If x <> 1 Then
    
        ' Combine both collections of factors and add x to the result.
        Factors = Factors & ", " & other_factors & x
    End If
End Function

 

[korhan]

Thanks for the explanation.

 

[footoo]

Thanks for the explanation.

The discussion in the link per post #2 is also interesting.