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

[bplus]

Hi Petr,

There are much simpler ways to do GCD:
https://rosettacode.org/wiki/Greatest_co...isor#BASIC

my favorite:

Code: (Select All)

_Title "GCD = Greatest Common Denominator" ' b+ 2020-05-21 from SB

While 1
    Input "enter a, b or 0 to quit "; a, b
    If a <> 0 And b <> 0 Then Print GCD(a, b) Else End
Wend

Function GCD (a As _Integer64, b As _Integer64)
    While a <> 0 And b <> 0
        If a > b Then a = a Mod b Else b = b Mod a
    Wend
    GCD = a + b
End Function

[Petr]

Hi Petr,

There are much simpler ways to do GCD:
https://rosettacode.org/wiki/Greatest_co...isor#BASIC

my favorite:

Code: (Select All)

_Title "GCD = Greatest Common Denominator" ' b+ 2020-05-21 from SB

While 1
    Input "enter a, b or 0 to quit "; a, b
    If a <> 0 And b <> 0 Then Print GCD(a, b) Else End
Wend

Function GCD (a As _Integer64, b As _Integer64)
    While a <> 0 And b <> 0
        If a > b Then a = a Mod b Else b = b Mod a
    Wend
    GCD = a + b
End Function

I just came and looking. Well, that's a beautiful example of how to do the same thing easily or complicatedly. And me (traditionally) chose the harder way Thanks for your version, BPlus. 

[bplus]

Well @Petr I gotta give you credit for your approach: factor both numbers find the factors in common. It would be how I would do it, like Steve did for reducing fractions. So I had to share this way I learned years ago.

Simplifying fractions is just as easy!

Code: (Select All)

_Define A-Z As INTEGER

While 1
    Input "Enter fraction to simplify as n/d, 0 quits "; fraction$
    slash = InStr(1, fraction$, "/")
    n = Val(Mid$(fraction$, 1, slash - 1))
    d = Val(Mid$(fraction$, slash + 1))
    If slash = 0 Or n = 0 Or d = 0 Then End
    g = gcd(n, d): sn = n / g: sd = d / g
    Print n; "/"; d; " simplifies to "; sn; "/"; sd
    Print
Wend

Function gcd (a, b)
    'a and b will be changed unless make copies
    c = a: d = b
    While c <> 0 And d <> 0
        If c > d Then c = c Mod d Else d = d Mod c
    Wend
    gcd = c + d
End Function