sieve.asm

;Tristan Madden
;10/17/2017

.386
.model flat, stdcall
.stack 4096
ExitProcess proto, dwExitCode:dword

.data

n DWORD 100000d                         ;I want to know all the primes before n

isPrime DWORD 0, 100000 DUP(?)          ;allocate n-bytes

endof BYTE 0

.code
main proc

; The first step of this program is to populate the "isPrime" array 
; with numbers, starting from n and working backwards down
; to 2.

mov ecx, n
mov esi, OFFSET isPrime + SIZEOF isPrime - TYPE isPrime

populate:
    
    mov [esi], ecx
    sub esi, SIZEOF DWORD
    CMP ecx, 2
    JE next1

loop populate

; At this stage, the "isPrime" array is populated with n-1 numbers, because
; we already know that 1 is not prime. The next step is to use a "nested for loop"
; that multiplies the counter of the inner-loop and the outter-loop, and set
; all of those multiples to 0 indicating that they are not prime.

next1:

mov ebx, 1                              ;32-bit outter-loop counter, 'i'
mov edi, 1                              ;32-bit inner-loop counter, 'j'

sieveOutterLoop:
    
    inc ebx
    mov eax, ebx                        ;calculate (i * i)
    mul ebx                             ;calculate (i * i)

    cmp eax, n                          ;end the program if (i*i) > n
    JG donezo                           ;end the program if (i*i) > n

    inc edi                             ;set inner-loop 'j' to outter-loop 'i'
    mov edi, ebx                        ;set inner-loop 'j' to outter-loop 'i'

    sieveInnerLoop:

        mov eax, ebx                    ;calculate (i * j)
        mul edi                         ;calculate (i * j)

        cmp eax, n                      ;compare (i * j) to n
        JG sieveOutterLoop

        mov esi, eax
        mov isPrime[esi * SIZEOF DWORD], 0
                
        inc edi
        inc ecx                         ;awful hack to keep the loop from breaking

    loop sieveInnerLoop

loop sieveOutterLoop

donezo:

; After I have sieved out the non-primes from the primes, I count the remaining
; values in the array that are not zero, and store that count in eax. 

mov ecx, n
mov eax, 0

counter:
    
    CMP isPrime[ecx * SIZEOF DWORD], 0
    JE dontAdd
    add eax, 1

    dontAdd:

loop counter

invoke ExitProcess,0
main endp
end main