The greatest common divisor of two numbers

[Petr]

Hi. I think this might be a useful feature for someone.

inspired by: https://demonstrations.wolfram.com/Findi...Factoring/

Code: (Select All)

NumA = 1000

NumB = 552

E = GreatestCommonDivisor(NumA, NumB)

Print "Greatest Common Divisor for"; NumA; "and"; NumB; " is:"; E

End





Function GreatestCommonDivisor& (A As Long, B As Long)

    If A = 0 And Abs(B) > 0 Then GreatestCommonDivisor& = B: Exit Function

    If B = 0 And Abs(A) > 0 Then GreatestCommonDivisor& = A: Exit Function

    If A = 0 And B = 0 Then GreatestCommonDivisor& = 0: Exit Function

    Dim As Long NrA(0)

    Dim As Long NrB(0)

    Dim As Long i, NrAI, NrBI, NumA, NumB



    NumA = A

    i = 1

    Do Until i >= NumA

        i = i + 1

        If NumA Mod i = 0 Then

            NumA = NumA \ i

            NrA(NrAI) = i

            NrAI = NrAI + 1

            ReDim _Preserve NrA(NrAI) As Long

            i = 1

        End If

    Loop



    NumB = B

    i = 1

    Do Until i >= NumB

        i = i + 1

        If NumB Mod i = 0 Then

            NumB = NumB \ i

            NrB(NrBI) = i

            NrBI = NrBI + 1

            ReDim _Preserve NrB(NrBI) As Long

            i = 1

        End If

    Loop



    Dim Outs(0) As Long

    Do Until ArrA = UBound(NrA) 

        If ArrA > UBound(NrA) Then Exit Do

        NumA = NrA(ArrA)

        ArrB = 0

        Do Until ArrB = UBound(NrB) 

            If ArrB > UBound(NrB) Then Exit Do

            NumB = NrB(ArrB)

            If NumA > 0 And NumB > 0 Then

                If NumA = NumB Then

                    Pass = 1

                    Outs(outI) = NumA

                    outI = outI + 1

                    ReDim _Preserve Outs(outI) As Long

                    NrA(ArrA) = -1 'just rewrite used numbers to wrong values (so the same valid is not used twice)

                    NrB(ArrB) = -1

                    Exit Do

                End If

            End If

            ArrB = ArrB + 1

        Loop

        ArrA = ArrA + 1

    Loop



    If UBound(Outs) > 0 Then

        ReDim _Preserve Outs(UBound(Outs) - 1) As Long

    End If

    Erase NrA

    Erase NrB

    If Pass = 0 Then

        GreatestCommonDivisor& = 1

        Erase Outs

        Exit Function

    End If

    'calculate greatest common divisor

    GCD& = Outs(0)

    For o = 1 To UBound(Outs)

        GCD& = GCD& * Outs(o)

    Next

    Erase Outs

    GreatestCommonDivisor& = GCD&

End Function