The greatest common divisor of two numbers

The greatest common divisor of two numbers - Printable Version

+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Prolific Programmers (https://qb64phoenix.com/forum/forumdisplay.php?fid=26)
+---- Forum: Petr (https://qb64phoenix.com/forum/forumdisplay.php?fid=52)
+---- Thread: The greatest common divisor of two numbers (/showthread.php?tid=3194)

The greatest common divisor of two numbers - Petr - 11-04-2024

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

inspired by: https://demonstrations.wolfram.com/FindingTheGreatestCommonDivisorOfTwoNumbersByFactoring/

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

RE: The greatest common divisor of two numbers - bplus - 11-04-2024

Hi Petr,

There are much simpler ways to do GCD:
https://rosettacode.org/wiki/Greatest_common_divisor#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

RE: The greatest common divisor of two numbers - Petr - 11-05-2024

(11-04-2024, 10:16 PM)bplus Wrote: Hi Petr,

There are much simpler ways to do GCD:
https://rosettacode.org/wiki/Greatest_common_divisor#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 Smile

Thanks for your version, BPlus. Big Grin

RE: The greatest common divisor of two numbers - bplus - 11-05-2024

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