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