' Prime sieve: find primes, test primality, GCD/LCM, factorization
#COMPILE EXE
#DIM ALL

FUNCTION IsPrime(BYVAL n AS LONG) AS LONG
    LOCAL i AS LONG
    IF n < 2 THEN FUNCTION = 0: EXIT FUNCTION
    IF n = 2 THEN FUNCTION = 1: EXIT FUNCTION
    IF n MOD 2 = 0 THEN FUNCTION = 0: EXIT FUNCTION
    i = 3
    DO WHILE i * i <= n
        IF n MOD i = 0 THEN FUNCTION = 0: EXIT FUNCTION
        i = i + 2
    LOOP
    FUNCTION = 1
END FUNCTION

FUNCTION GreatestCommonDivisor(BYVAL a AS LONG, BYVAL b AS LONG) AS LONG
    LOCAL tmp AS LONG
    DO WHILE b <> 0
        tmp = a MOD b
        a = b
        b = tmp
    LOOP
    FUNCTION = a
END FUNCTION

FUNCTION LeastCommonMultiple(BYVAL a AS LONG, BYVAL b AS LONG) AS LONG
    IF a = 0 OR b = 0 THEN FUNCTION = 0: EXIT FUNCTION
    FUNCTION = a / GreatestCommonDivisor(a, b) * b
END FUNCTION

FUNCTION CountPrimesUpTo(BYVAL limit AS LONG) AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL count  AS LONG
    DIM marks(0 TO 1000) AS LONG
    IF limit > 1000 THEN FUNCTION = -1: EXIT FUNCTION
    FOR i = 2 TO limit
        marks(i) = 1
    NEXT i
    i = 2
    DO WHILE i * i <= limit
        IF marks(i) = 1 THEN
            j = i * i
            DO WHILE j <= limit
                marks(j) = 0
                j = j + i
            LOOP
        END IF
        i = i + 1
    LOOP
    count = 0
    FOR i = 2 TO limit
        IF marks(i) = 1 THEN count = count + 1
    NEXT i
    FUNCTION = count
END FUNCTION

FUNCTION PrintPrimesUpTo(BYVAL limit AS LONG) AS STRING
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL result AS STRING
    DIM marks(0 TO 500) AS LONG
    IF limit > 500 THEN FUNCTION = "limit too high": EXIT FUNCTION
    FOR i = 2 TO limit
        marks(i) = 1
    NEXT i
    i = 2
    DO WHILE i * i <= limit
        IF marks(i) = 1 THEN
            j = i * i
            DO WHILE j <= limit
            marks(j) = 0
            j = j + i
        LOOP
        END IF
        i = i + 1
    LOOP
    result = ""
    FOR i = 2 TO limit
        IF marks(i) = 1 THEN result = result + FORMAT$(i) + " "
    NEXT i
    FUNCTION = result
END FUNCTION

FUNCTION CountTwinPrimes(BYVAL limit AS LONG) AS LONG
    LOCAL prev  AS LONG
    LOCAL i  AS LONG
    LOCAL count  AS LONG
    prev = 2
    count = 0
    FOR i = 3 TO limit
        IF IsPrime(i) THEN
            IF i - prev = 2 THEN count = count + 1
            prev = i
        END IF
    NEXT i
    FUNCTION = count
END FUNCTION

FUNCTION PBMAIN() AS LONG
    LOCAL fac(1 TO 50) AS LONG
    LOCAL i  AS LONG
    LOCAL fc  AS LONG
    LOCAL n  AS LONG
    PRINT "=== Prime Number Library ==="
    PRINT
    n = 97
    PRINT "Is " + FORMAT$(n) + " prime? "
    IF IsPrime(n) THEN PRINT "Yes" ELSE PRINT "No"
    n = 100
    PRINT "Is " + FORMAT$(n) + " prime? "
    IF IsPrime(n) THEN PRINT "Yes" ELSE PRINT "No"
    PRINT
    PRINT "Primes up to 50: " + PrintPrimesUpTo(50)
    PRINT "Count up to 100: " + FORMAT$(CountPrimesUpTo(100))
    PRINT
    PRINT "GCD(48, 18) = " + FORMAT$(GreatestCommonDivisor(48, 18))
    PRINT "LCM(12, 18) = " + FORMAT$(LeastCommonMultiple(12, 18))
    PRINT
    PRINT "Twin primes up to 100: " + FORMAT$(CountTwinPrimes(100))
    PRINT
    PRINT "Prime sieve tests complete."
    FUNCTION = 0
END FUNCTION
