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
- Create a boolean array
sieve[0..N], all initialised to 0 (“is prime”). - Start with
p = 2(the first prime). - Mark every multiple of
pfromp*pup toNas composite (set to 1). - Advance
pto the next index still marked 0. - Repeat until
p * p > N. - 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
- 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. - Outer loop termination —
MUL CXcomputes 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. - Base-indexed addressing —
sieve[BX]uses the direct base addressing mode: DS:BX + displacement ofsieve. BX holds the current index CX or SI as a 16-bit offset. - 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.
- Print phase — iterates from index 2 to LIMIT; any index whose sieve byte is still 0 is printed using the stack-based
PRINT_DECIMALprocedure 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
| Mistake | Symptom | Fix |
|---|---|---|
Using CX as both outer loop counter and LOOP in PRINT_DECIMAL | Corrupted prime counter | Save/restore CX around the PRINT_DECIMAL call, or rename loop variable |
Starting inner loop at 2*p instead of p*p | Correct result but slower than necessary | Initialise SI = AX (which holds p² from the outer MUL) |
Forgetting XOR DX, DX before DIV in PRINT_DECIMAL | Wrong decimal output | Always zero DX before unsigned 16-bit division |
Using SI without preserving it across INT calls | Random behaviour | BIOS/DOS may clobber SI; push/pop around INT 21h calls if needed |
See Also
- 8086 Assembly Program to Implement a Simple Calculator
- 8086 Assembly: GCD Using Euclidean Algorithm
- 8086 Assembly: Factorial Using Recursion
- Introduction to Memory Segmentation in 8086
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.
No Comments yet!