' GCD and LCM — computes greatest common divisor and least common multiple
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL a AS LONG
    LOCAL b AS LONG
    LOCAL x AS LONG
    LOCAL y AS LONG
    LOCAL temp AS LONG
    LOCAL gcdVal AS LONG
    LOCAL lcmVal AS LONG
    LOCAL remainder AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL m AS LONG
    LOCAL n AS LONG
    LOCAL testA AS LONG
    LOCAL testB AS LONG
    LOCAL expectedGcd AS LONG
    LOCAL expectedLcm AS LONG
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    LOCAL lineStr AS STRING
    testCount = 0
    passCount = 0
    failCount = 0
    PRINT "============================================"
    PRINT "      GCD AND LCM CALCULATOR"
    PRINT "============================================"
    PRINT ""
    PRINT "Euclidean algorithm for GCD"
    PRINT ""
    a = 48
    b = 18
    x = a
    y = b
    DO WHILE y <> 0
        remainder = x MOD y
        x = y
        y = remainder
    LOOP
    gcdVal = x
    lcmVal = (a / gcdVal) * b
    PRINT "GCD(" + STR$(a) + ", " + STR$(b) + ") = " + STR$(gcdVal)
    PRINT "LCM(" + STR$(a) + ", " + STR$(b) + ") = " + STR$(lcmVal)
    testCount = testCount + 1
    IF gcdVal = 6 THEN
        passCount = passCount + 1
    ELSE
        failCount = failCount + 1
    END IF
    PRINT ""
    a = 1071
    b = 462
    x = a
    y = b
    DO WHILE y <> 0
        remainder = x MOD y
        x = y
        y = remainder
    LOOP
    gcdVal = x
    IF y = 0 THEN
        y = 1
    END IF
    lcmVal = (a / gcdVal) * b
    PRINT "GCD(" + STR$(a) + ", " + STR$(b) + ") = " + STR$(gcdVal)
    PRINT "LCM(" + STR$(a) + ", " + STR$(b) + ") = " + STR$(lcmVal)
    testCount = testCount + 1
    IF gcdVal = 21 THEN
        passCount = passCount + 1
    ELSE
        failCount = failCount + 1
    END IF
    PRINT ""
    a = 123456
    b = 7890
    x = a
    y = b
    DO WHILE y <> 0
        remainder = x MOD y
        x = y
        y = remainder
    LOOP
    gcdVal = x
    lcmVal = (a / gcdVal) * b
    PRINT "GCD(" + STR$(a) + ", " + STR$(b) + ") = " + STR$(gcdVal)
    PRINT "LCM(" + STR$(a) + ", " + STR$(b) + ") = " + STR$(lcmVal)
    PRINT ""
    PRINT "============================================"
    PRINT "      DOUBLE EUCLIDEAN ALGORITHM"
    PRINT "============================================"
    PRINT ""
    LOCAL s AS LONG
    LOCAL t AS LONG
    LOCAL s1 AS LONG
    LOCAL s2 AS LONG
    LOCAL t1 AS LONG
    LOCAL t2 AS LONG
    LOCAL q AS LONG
    LOCAL r AS LONG
    a = 120
    b = 23
    x = a
    y = b
    s1 = 1
    s2 = 0
    t1 = 0
    t2 = 1
    DO WHILE y <> 0
        q = x / y
        r = x MOD y
        s = s1 - q * s2
        t = t1 - q * t2
        x = y
        y = r
        s1 = s2
        s2 = s
        t1 = t2
        t2 = t
    LOOP
    gcdVal = x
    PRINT "DOUBLE GCD(" + STR$(a) + ", " + STR$(b) + "):"
    PRINT "  gcd = " + STR$(gcdVal)
    PRINT "  s = " + STR$(s1)
    PRINT "  t = " + STR$(t1)
    PRINT "  Verification: " + STR$(a) + "*" + STR$(s1) + " + " + STR$(b) + "*" + STR$(t1) + " = " + STR$(a * s1 + b * t1)
    testCount = testCount + 1
    IF a * s1 + b * t1 = gcdVal THEN
        passCount = passCount + 1
    ELSE
        failCount = failCount + 1
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "      GCD OF MULTIPLE NUMBERS"
    PRINT "============================================"
    PRINT ""
    LOCAL values(100) AS LONG
    LOCAL numCount AS LONG
    values(0) = 12
    values(1) = 24
    values(2) = 36
    values(3) = 48
    values(4) = 60
    numCount = 5
    gcdVal = values(0)
    FOR i = 1 TO numCount - 1
        x = gcdVal
        y = values(i)
        DO WHILE y <> 0
            remainder = x MOD y
            x = y
            y = remainder
        LOOP
        gcdVal = x
    NEXT i
    PRINT "GCD of [12, 24, 36, 48, 60] = " + STR$(gcdVal)
    testCount = testCount + 1
    IF gcdVal = 12 THEN
        passCount = passCount + 1
    ELSE
        failCount = failCount + 1
    END IF
    lcmVal = values(0)
    FOR i = 1 TO numCount - 1
        a = lcmVal
        b = values(i)
        x = a
        y = b
        DO WHILE y <> 0
            remainder = x MOD y
            x = y
            y = remainder
        LOOP
        gcdVal = x
        lcmVal = (a / gcdVal) * b
    NEXT i
    PRINT "LCM of [12, 24, 36, 48, 60] = " + STR$(lcmVal)
    PRINT ""
    PRINT "============================================"
    PRINT "      COPRIME CHECK (gcd = 1)"
    PRINT "============================================"
    PRINT ""
    FOR i = 1 TO 20
        FOR j = 1 TO 20
            x = i
            y = j
            DO WHILE y <> 0
                remainder = x MOD y
                x = y
                y = remainder
            LOOP
            gcdVal = x
            IF gcdVal = 1 THEN
                PRINT STR$(i) + " and " + STR$(j) + " are coprime"
            END IF
        NEXT j
    NEXT i
    PRINT ""
    PRINT "============================================"
    PRINT "      LCM VERIFICATION"
    PRINT "============================================"
    PRINT ""
    FOR a = 2 TO 12
        FOR b = 2 TO 12
            x = a
            y = b
            DO WHILE y <> 0
                remainder = x MOD y
                x = y
                y = remainder
            LOOP
            gcdVal = x
            lcmVal = (a / gcdVal) * b
            testCount = testCount + 1
            IF lcmVal MOD a = 0 AND lcmVal MOD b = 0 THEN
                passCount = passCount + 1
            ELSE
                failCount = failCount + 1
            END IF
        NEXT b
    NEXT a
    PRINT "Verification: " + STR$(passCount) + " passed, " + STR$(failCount) + " failed of " + STR$(testCount)
    FUNCTION = 0
END FUNCTION
