8086

8086 Assembly Program to Find Prime Numbers Using the Sieve of Eratosthenes

Leave a comment

The Sieve of Eratosthenes is one of the oldest and most elegant algorithms for finding all prime numbers up to a given limit. Implementing it in 8086 assembly is an outstanding exercise: it demands careful use of nested loops, indirect memory addressing through BX, and byte-level array manipulation — concepts that appear throughout real-mode system programming. This post walks through a fully working implementation that marks composite numbers in a byte array and then prints every surviving prime.

Algorithm Recap

  1. Create a boolean array sieve[0..N], all initialised to 0 (“is prime”).
  2. Start with p = 2 (the first prime).
  3. Mark every multiple of p from p*p up to N as composite (set to 1).
  4. Advance p to the next index still marked 0.
  5. Repeat until p * p > N.
  6. Every index still holding 0 is a prime number.

Complete 8086 Assembly Program

.MODEL SMALL
.STACK 200h

LIMIT EQU 50                    ; find primes up to LIMIT

.DATA
    sieve     DB (LIMIT+1) DUP(0)  ; 0 = prime candidate, 1 = composite
    msg_hdr   DB 'Primes up to 50: $'
    msg_space DB ' $'
    msg_newln DB 0Dh, 0Ah, '$'

.CODE
MAIN PROC
    MOV  AX, @DATA
    MOV  DS, AX

    ; ============================================================
    ; PHASE 1: Mark composites
    ; Outer loop: p = 2 .. sqrt(LIMIT) ~= 7
    ; ============================================================
    MOV  CX, 2                  ; CX = current prime candidate p

OUTER_LOOP:
    ; Check CX*CX  LIMIT  → sieve complete

    ; Skip p if already marked composite
    MOV  BX, CX
    MOV  AL, sieve[BX]          ; base-indexed addressing
    CMP  AL, 1
    JE   NEXT_P                 ; already composite → skip

    ; Inner loop: mark multiples of p starting at p*p
    ; AX still holds p*p from MUL above
    MOV  SI, AX                 ; SI = p*p  (first multiple to mark)

INNER_LOOP:
    CMP  SI, LIMIT
    JA   NEXT_P                 ; past limit — done with this p

    MOV  BX, SI
    MOV  BYTE PTR sieve[BX], 1  ; mark sieve[SI] as composite

    ADD  SI, CX                 ; SI += p  (next multiple)
    JMP  INNER_LOOP

NEXT_P:
    INC  CX                     ; try next candidate
    JMP  OUTER_LOOP

SIEVE_DONE:

    ; ============================================================
    ; PHASE 2: Print all primes
    ; ============================================================
    LEA  DX, msg_hdr
    MOV  AH, 09h
    INT  21h

    LEA  DX, msg_newln
    MOV  AH, 09h
    INT  21h

    MOV  CX, 2                  ; check from index 2

PRINT_LOOP:
    CMP  CX, LIMIT
    JA   EXIT_PROG

    MOV  BX, CX
    MOV  AL, sieve[BX]
    CMP  AL, 0                  ; 0 means still prime
    JNE  SKIP_PRINT

    ; Print CX as decimal
    MOV  AX, CX
    CALL PRINT_DECIMAL

    LEA  DX, msg_space
    MOV  AH, 09h
    INT  21h

SKIP_PRINT:
    INC  CX
    JMP  PRINT_LOOP

EXIT_PROG:
    LEA  DX, msg_newln
    MOV  AH, 09h
    INT  21h

    MOV  AH, 4Ch
    INT  21h
MAIN ENDP

; -------------------------------------------------------
; PRINT_DECIMAL: prints unsigned decimal in AX (0-99)
; -------------------------------------------------------
PRINT_DECIMAL PROC
    MOV  BX, 10
    XOR  CX, CX

PD_DIVIDE:
    XOR  DX, DX
    DIV  BX                     ; AX = AX/10, DX = AX%10
    PUSH DX
    INC  CX
    CMP  AX, 0
    JNE  PD_DIVIDE

PD_PRINT:
    POP  DX
    ADD  DL, '0'
    MOV  AH, 02h
    INT  21h
    LOOP PD_PRINT

    RET
PRINT_DECIMAL ENDP

END MAIN

How the Code Works

  1. sieve array initialisation — DB (LIMIT+1) DUP(0) allocates 51 bytes in the data segment, all set to 0. Each byte represents one integer from 0 to 50.
  2. Outer loop termination — MUL CX computes p². When p² exceeds LIMIT the sieve is complete; all remaining 0-entries are prime. This avoids the square-root calculation the algorithm technically requires.
  3. Base-indexed addressing — sieve[BX] uses the direct base addressing mode: DS:BX + displacement of sieve. BX holds the current index CX or SI as a 16-bit offset.
  4. Inner loop — marks every multiple of the current prime p starting from p². Starting at p² (not 2p) is the Sieve’s key optimisation: all smaller multiples were already marked by earlier primes.
  5. Print phase — iterates from index 2 to LIMIT; any index whose sieve byte is still 0 is printed using the stack-based PRINT_DECIMAL procedure shared with the calculator post.

Sample Output

Primes up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Extending the Limit

To raise the limit, change only the LIMIT EQU constant. The sieve array grows automatically via DUP. For limits above 255, the PRINT_DECIMAL procedure already handles multi-digit output correctly. The maximum practical limit for a .MODEL SMALL program is around 32,000 — well within the 64 KB data segment.

Common Mistakes

MistakeSymptomFix
Using CX as both outer loop counter and LOOP in PRINT_DECIMALCorrupted prime counterSave/restore CX around the PRINT_DECIMAL call, or rename loop variable
Starting inner loop at 2*p instead of p*pCorrect result but slower than necessaryInitialise SI = AX (which holds p² from the outer MUL)
Forgetting XOR DX, DX before DIV in PRINT_DECIMALWrong decimal outputAlways zero DX before unsigned 16-bit division
Using SI without preserving it across INT callsRandom behaviourBIOS/DOS may clobber SI; push/pop around INT 21h calls if needed

See Also

Conclusion

The Sieve of Eratosthenes in 8086 assembly showcases several powerful low-level techniques: using EQU for easily adjustable constants, initialising arrays with DUP, exploiting base-indexed addressing for efficient array access, and applying the p² starting-point optimisation that makes the sieve fast in any language. The same program structure — initialise, sieve, output — scales cleanly to larger limits simply by changing the LIMIT constant.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.