Sieve of Eratosthenes

[zedd151]

My 32 bit (original) version of Sieve of Eratosthenes... (added message box, if array not allocated.)

Code Select Expand

    include \masm32\include\masm32rt.inc
   
    .data
   
    pTbl        dd 0                    ; <-- pointer to byte array
    arrsize    dd 1000000
    curnumber  dd 0                    ; <-- current number for our sieve algo
   
    .code
start:
   
    invoke GlobalAlloc, GPTR, arrsize  ; <-- allocate memory for table and prime numbers
  .if eax == 0                          ; <-- if not enough memory for array size, display message and exit
 
    fn MessageBox, 0, "Not enough memory to create array", 0, 0
    jmp noarray
  .endif
    mov pTbl, eax
   
    push edi
    mov edi, pTbl                      ; temporarily put ptr to array in edi, for stosb
    mov eax, 01010101h
    mov ecx, arrsize
    shr ecx, 2
    rep stosd                          ; <-- initialize the table to '1'
    pop edi                            ; <-- restore edi to previous value
    mov esi, pTbl                      ; <-- we put ptr to array into esi :)
   
    xor eax, eax
    mov curnumber, 2                    ; <-- exluding '0' and '1', as neither are prime
    add eax, curnumber                  ; <-- exclude the first iteration of sequence
                                        ; <-- else we will have no primes listed
  @@:
    add eax, curnumber                  ; <-- get multiples for this iteration
    cmp eax, arrsize                    ; <-- check if end of array is reached, exit
    jae done1                          ;    loop if yes.
    cmp byte ptr [esi+eax], 0          ; <-- check if array location is already marked
    jz @b
    mov byte ptr [esi+eax], 0          ; <-- if not marked, we mark it now
    jmp @b
   
  done1:
    inc curnumber                      ; <-- increment current number
    mov eax, curnumber                  ; <-- move it into register
    cmp eax, arrsize                    ; <-- check if at array end
    jae done2                          ; <-- jump to next process, if array end
    xor eax, eax                        ;    else increment to next number
    add eax, curnumber
    jmp @b                              ; <-- jump back into the processing loop
   
  done2:
    mov edi, 2                          ; <--- skip over '0' and '1'
  @@:
   
    cmp byte ptr [esi+edi], 1          ; <--- if byte == zero, not prime, don't print
    jnz noprint
   
    mov eax, ustr$(edi)                ; <--- convert our current prime to ascii decimal string
   
    pushad                              ; <--- save all the registers

    print eax, 0Dh, 0Ah, 0
   
    popad                              ; <--- restore the registers
   
  noprint:
    inc edi
    cmp edi, arrsize
    jl @b                              ; <--- loop back to get more primes to print
    invoke GlobalFree, pTbl            ; <--- free the memory used

  noarray:                              ; <--- jump here to exit, if memory not allocated
    invoke ExitProcess, 0
end start

Use the included "makeit.bat" to assemble and link it, and "RunIt.bat" to run the program, generate file "primes32.txt", and open the .txt file with qeditor.

You're Welcome.