Prime algorithm in assembler

One of the greatest strengths of assembly language is the extreme compactness of code. Digging though my old files I found this gem that prints all prime numbers under 2^32. The COM file size is 165 bytes. That's right! You could memorize the bytes if you wanted to and hand assemble it.

The algorithm is not sieve (which would create 2^31 locations and strike off multiples of primes). Rather this is a space optimized algorithm that repeatedly divides each number n from 2 to sqrt(n) to determine if a number is prime. This algorithm uses no additional storage than the 165 bytes to hold the code.



.model tiny
.code
.386
        org     100h
start:
main    proc
        xor     eax,eax
        mov     al,3
@@m2:
        call    isprime
        jnc     @@m1
        call    printdword
        call    printcrlf
@@m1:
        inc     eax
        jnz     @@m2


        mov     ax,4c00h
        int     21h
main    endp


isprime proc
        pushad
        mov     esi,eax         ; save number
        xor     ecx,ecx
        mov     ebx,ecx
        mov     edx,ecx         ; edx = 0
        call    sqrt
        mov     cx,ax           ; save sqrt
        mov     bl,2            ; ebx = 2 (divisor)
@@i2:
        mov     eax,esi         ; restore number
        cmp     ecx,ebx         ; is sqrt < divisor?
        jl      @@i4            ; yes, no need to divide any more
        div     ebx
        or      edx,edx
        jz      @@i1
        xor     edx,edx
        inc     ebx
        jnz     @@i2
@@i4:
        stc
        jmp     @@i3
@@i1:
        clc
@@i3:
        popad
        ret
isprime endp


sqrt    proc
        push    ebx
        push    ecx


        xor     ecx,ecx
        mov     ebx,ecx
@@s2:
        inc     ebx
        sub     eax,ebx
        jl      @@s1
        inc     cx
        inc     ebx
        jmp     @@s2
@@s1:
        mov     ax,cx


        pop     ecx
        pop     ebx
        ret
sqrt    endp


printdword      proc
        pushad
        xor     ebx,ebx
        mov     cx,bx
        mov     bl,10
@@p1:
        xor     edx,edx
        div     ebx
        push    dx
        inc     cx
        or      eax,eax
        jnz     @@p1
@@p2:
        pop     ax
        add     al,'0'
        mov     dl,al
        mov     ah,02
        int     21h
        loop    @@p2


        popad
        ret
printdword      endp

printcrlf       proc

        pusha

        mov     dl,13

        mov     ah,02

        int     21h

        mov     dl,10

        mov     ah,2

        int     21h

        popa

        ret

printcrlf       endp

        end     start