' Prime Number Generation — Sieve of Eratosthenes and related algorithms
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL limit AS LONG
    LOCAL sieve(10000) AS LONG
    LOCAL primes(5000) AS LONG
    LOCAL primeCount AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL p AS LONG
    LOCAL isPrimeVal AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    limit = 1000
    PRINT "============================================"
    PRINT "     PRIME NUMBER GENERATION"
    PRINT "============================================"
    PRINT ""
    PRINT "Sieve of Eratosthenes up to " + STR$(limit)
    PRINT ""
    FOR i = 2 TO limit
        sieve(i) = 1
    NEXT i
    p = 2
    DO WHILE p * p <= limit
        IF sieve(p) = 1 THEN
            j = p * p
            DO WHILE j <= limit
                sieve(j) = 0
                j = j + p
            LOOP
        END IF
        p = p + 1
    LOOP
    primeCount = 0
    FOR i = 2 TO limit
        IF sieve(i) = 1 THEN
            primes(primeCount) = i
            primeCount = primeCount + 1
        END IF
    NEXT i
    PRINT "Primes up to " + STR$(limit) + " (" + STR$(primeCount) + " found):"
    PRINT ""
    lineStr = ""
    FOR i = 0 TO primeCount - 1
        elemStr = STR$(primes(i))
        DO WHILE LEN(elemStr) < 4
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     PRIMALITY TEST (trial division)"
    PRINT "============================================"
    PRINT ""
    FOR i = 2 TO 100
        isPrimeVal = 1
        j = 2
        DO WHILE j * j <= i
            IF i MOD j = 0 THEN
                isPrimeVal = 0
                EXIT DO
            END IF
            j = j + 1
        LOOP
        IF isPrimeVal = 1 THEN
            PRINT STR$(i) + " is prime"
        END IF
    NEXT i
    PRINT ""
    PRINT "============================================"
    PRINT "     SEGMENTED SIEVE (small range)"
    PRINT "============================================"
    PRINT ""
    LOCAL low AS LONG
    LOCAL high AS LONG
    LOCAL segment(1000) AS LONG
    LOCAL segLen AS LONG
    LOCAL first AS LONG
    low = 100
    high = 200
    segLen = high - low + 1
    FOR i = 0 TO segLen - 1
        segment(i) = 1
    NEXT i
    FOR i = 0 TO primeCount - 1
        p = primes(i)
        IF p * p > high THEN
            EXIT FOR
        END IF
        first = (low / p) * p
        IF first < low THEN
            first = first + p
        END IF
        IF first = p THEN
            first = first + p
        END IF
        j = first
        DO WHILE j <= high
            segment(j - low) = 0
            j = j + p
        LOOP
    NEXT i
    PRINT "Primes in range [" + STR$(low) + "-" + STR$(high) + "]:"
    lineStr = ""
    FOR i = 0 TO segLen - 1
        IF segment(i) = 1 THEN
            elemStr = STR$(low + i)
            DO WHILE LEN(elemStr) < 4
                elemStr = " " + elemStr
            LOOP
            lineStr = lineStr + elemStr + " "
        END IF
    NEXT i
    PRINT lineStr
    PRINT ""
    PRINT "============================================"
    PRINT "     FACTORIZATION (prime factors)"
    PRINT "============================================"
    PRINT ""
    LOCAL n AS LONG
    LOCAL factors(100) AS LONG
    LOCAL factorCount AS LONG
    LOCAL remaining AS LONG
    FOR n = 12 TO 60
        remaining = n
        factorCount = 0
        i = 0
        DO WHILE i < primeCount AND primes(i) * primes(i) <= remaining
            DO WHILE remaining MOD primes(i) = 0
                factors(factorCount) = primes(i)
                factorCount = factorCount + 1
                remaining = remaining / primes(i)
            LOOP
            i = i + 1
        LOOP
        IF remaining > 1 THEN
            factors(factorCount) = remaining
            factorCount = factorCount + 1
        END IF
        PRINT STR$(n) + " = "
        FOR j = 0 TO factorCount - 1
            PRINT STR$(factors(j))
            IF j < factorCount - 1 THEN
                PRINT " * "
            END IF
        NEXT j
        PRINT ""
    NEXT n
    PRINT ""
    PRINT "============================================"
    PRINT "     TWIN PRIMES (difference of 2)"
    PRINT "============================================"
    PRINT ""
    limit = 500
    FOR i = 2 TO limit - 2
        IF sieve(i) = 1 AND sieve(i + 2) = 1 THEN
            PRINT "(" + STR$(i) + ", " + STR$(i + 2) + ")"
        END IF
    NEXT i
    PRINT ""
    PRINT "============================================"
    PRINT "     PRIME SUMS (Goldbach conjecture)"
    PRINT "============================================"
    PRINT ""
    LOCAL evenNum AS LONG
    LOCAL foundPair AS LONG
    FOR evenNum = 4 TO 50 STEP 2
        foundPair = 0
        FOR i = 0 TO primeCount - 1
            IF primes(i) > evenNum / 2 THEN
                EXIT FOR
            END IF
            j = evenNum - primes(i)
            IF sieve(j) = 1 THEN
                PRINT STR$(evenNum) + " = " + STR$(primes(i)) + " + " + STR$(j)
                foundPair = 1
                EXIT FOR
            END IF
        NEXT i
        IF foundPair = 0 THEN
            PRINT STR$(evenNum) + " = no pair found"
        END IF
    NEXT evenNum
    PRINT ""
    PRINT "First " + STR$(primeCount) + " primes up to " + STR$(limit)
    FUNCTION = 0
END FUNCTION
