### Author Topic: Sieve of Eratosthenes - Print Prime Numbers  (Read 11543 times)

#### Mathi

• Jr. Member
• Posts: 82
• Country:
##### Sieve of Eratosthenes - Print Prime Numbers
« on: January 26, 2012, 06:39:32 PM »
Sieve of Eratosthenes:
Algorithm for finding all prime numbers up to MAX LIMIT (2^32 - 1). (ASM implementation).

Reference:
http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.cpp

Reference for Integer sqroot:
http://www.azillionmonkeys.com/qed/sqroot.html

Usage : Sieve  <integer>

eg:
C:\NASM> Sieve 13
2
3
5
7
11
13
Number of Primes = 6

Code: [Select]
`;;;;C++ Version for Reference;;;;http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.cpp;;;;#include <cmath>;;;;#include <vector>;;;; ;;;;/*primes is a list of primes, n is all the primes you want to generate.. from 2 to n*/;;;;void genPrimes(vector<int>&primes,int n){;;;; for(int i=2;i<=n;i++){;;;; int root=int(sqrt(i))+1;    /*remember the square root*/;;;; bool found=false;       /*prime found?*/;;;; for(vector<int>::const_iterator it = primes.begin();it!=primes.end()&& *it<root;it++){;;;; if(i% *it==0){found=true;break;} /*this is not prime*/;;;; };;;; if(!found)primes.push_back(i); /*this is a prime*/;;;; };;;;};;;;  Reference for isqrt ;;;;  http://www.azillionmonkeys.com/qed/sqroot.html;;;;*********************;;;;Assemble with :;;;;nasm -fobj Sieve.asm;;;;Link with;;;;alink -c -oPE -subsys con Sieve;;;;Usage eg: Sieve 2000;;;;*********************%include "win32n.inc";;================================;; MACRO  str2int     int2str by Written by mastercpp.;;================================%macro str2int 1        push    ebx ;        push    esi ;        push    edi ;        mov ebx, 0        mov ecx, 0        xor eax,eax        mov ebx,0000000Ah        mov esi, %1        %%ConvertLoop:        movzx ecx,byte [esi] ;Zeichen laden.        test ecx,ecx        jz  short %%ExitConvertLoop ;0 => Exit        inc esi        sub cl,30h ;0-9...        mul ebx ;Ergebnis * 10        add eax,ecx ;+ nÃ¤chste Ziffer        jmp short %%ConvertLoop        %%ExitConvertLoop:        pop     edi        pop     esi        pop     ebx%endmacro%macro int2str 2        push    ebx ;        push    esi ;        push    edi ;        %%start:        mov  eax, %1        xor  ecx, ecx        mov  ebx, 000ah        %%DecConvert:        xor  edx,  edx        div  ebx        add  edx,  0030h        push edx        inc  ecx        or   eax,  eax        jnz  short %%DecConvert        mov  edi,  %2        mov edx,ecx        %%SortDec:        pop   eax        stosb        loop  %%SortDec        mov eax, 0h        stosb        pop     edi        pop     esi        pop     ebx%endmacro;;================================;; mastercpp  end macros;;================================extern GlobalAllocimport GlobalAlloc kernel32.dllextern GlobalFreeimport GlobalFree kernel32.dllextern ExitProcessimport ExitProcess kernel32.dllextern GetStdHandleimport GetStdHandle kernel32.dllextern WriteFileimport WriteFile kernel32.dllextern GetCommandLineAimport GetCommandLineA kernel32.dllglobal ..startsegment .bss USE32buffer resb 32segment .data USE32PrimeListHdl dd 0;Root dd 0;FoundFactor dd 0input1 db "1000",0value dd 0consolehdl dd 0byteswritten dd 0noofprimes dd 0newline db 10newlineLEN equ 1message1 db "Number of Primes = "MSG1_LEN equ \$-message1message2 db "Usage : Sieve <integer>    ",13,10,"MAX 2^32 - 1 ",13,10MSG2_LEN equ \$-message2segment .code USE32 class=code..start:; hStdOut = GetstdHandle( STD_OUTPUT_HANDLE)push    dword STD_OUTPUT_HANDLEcall    [GetStdHandle]mov     [consolehdl], eax    ;; Command line parsing - STARTcall [GetCommandLineA]mov esi,eaxNextChar:lodsbcmp al,' 'jnz CheckNulljmp SkipSpacesCheckNull:cmp al,0jnz NextChar ;;; No Parameter - print usage text push    dword 0 push    dword byteswritten push    MSG2_LEN push    dword message2 push    dword [consolehdl] call    [WriteFile] push dword 0 call [ExitProcess]SkipSpaces:lodsbcmp al,' 'jz SkipSpacesdec esi;; Command line parsing - ENDstr2int esimov [value],eaxpush eaxcall IntegerLn   ;;calculate Integer Logarithm.add esp,4mov ebx,eaxmov eax, 2test ebx,ebxjz AllocateMemoryxor edx,edxmov eax,[value]div ebx  ;;; EAX stores the quotient of N/Ln(N)AllocateMemory:shl eax,1  ;;;Multiply by 2.   Just to make sure we have enough memoryimul eax,4 ;;;  N number of DWORDSpush eaxpush dword GPTRcall [GlobalAlloc]mov [PrimeListHdl],eaxmov edi,eaxmov ecx,2StartDivisorLoop: cmp ecx,[value] jg ExitDivisorsLoop push edi  ;;;  Save EDI push ecx  ;;;  Save ECX mov eax,ecx push eax call IntegerSqrt add esp,4 inc eax mov [Root],eax mov dword[FoundFactor],0 pop ecx   ;;;  Restore ECX pop edi mov esi,[PrimeListHdl]StartInnerLoop: lodsd test eax,eax jnz CheckLessThanRoot jmp CheckFoundFactorCheckLessThanRoot: cmp eax,[Root] jge CheckFoundFactor push ecx xchg eax,ecx xor edx,edx div ecx pop ecx test edx,edx jnz NotFactor mov dword[FoundFactor],1 jmp CheckFoundFactor NotFactor: jmp StartInnerLoopCheckFoundFactor: cmp dword[FoundFactor],1 jz NotPrime mov eax,ecx stosdNotPrime: inc ecx jmp StartDivisorLoopExitDivisorsLoop: mov eax,0 stosd mov esi,[PrimeListHdl] xor ebx,ebxPrintLoop:         lodsd test eax,eax jz ExitOut        int2str eax,buffer pusha ; WriteFile( hstdOut, message, length(message), &bytes, 0); push    dword 0 push    dword byteswritten push    edx push    buffer push    dword [consolehdl] call    [WriteFile] ; WriteFile( hstdOut, "\n", 2, &bytes, 0); push    dword 0 push    dword byteswritten push    dword 1 push    newline push    dword [consolehdl] call    [WriteFile] popa inc ebx jmp PrintLoopExitOut: mov [noofprimes],ebx push    dword 0 push    dword byteswritten push    MSG1_LEN push    message1 push    dword [consolehdl] call    [WriteFile] int2str [noofprimes],buffer push    dword 0 push    dword byteswritten push    edx push    buffer push    dword [consolehdl] call    [WriteFile] push dword [PrimeListHdl] call [GlobalFree] push dword 0 call [ExitProcess]IntegerLn: push ebp mov ebp,esp xor ecx,ecx mov eax,[ebp+8] DivideBy2: shr eax,1 test eax,eax jz IntegerLn_exit inc ecx jmp DivideBy2IntegerLn_exit: mov eax,ecx leave ret IntegerSqrt: push ebp mov ebp,esp xor edi,edi mov ebx,0x8000 mov ecx,15startloop: mov esi,edi shl esi,1 mov edx,esi add edx,ebx shl edx,cl dec ecx cmp eax,edx jl shiftrightb add edi,ebx sub eax,edx shiftrightb: shr ebx,1 cmp ebx,0 jg startloop mov eax,edi leave ret `
I have attached a version using nagoa macros too.
« Last Edit: February 09, 2012, 08:18:06 PM by Mathi »