Changed the topic title, to reflect that several variations are available in this topic, by several authors. If you have a different Prime Sieve, post your code here and join the phun. :biggrin:
My 32 bit (original) version of Sieve of Eratosthenes... (added message box, if array not allocated.)
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. :biggrin:
Great stuff, Zedd :thumbsup:
Quote from: jj2007 on February 23, 2025, 11:03:21 AMGreat stuff, Zedd :thumbsup:
Thanks, but it is actually old code, I found it recently ('prime' was nowhere in its original name :tongue: ). Previously, I only knew where my more recent 64 bit version was. :smiley:
Hi,
I wrote a program to display primes as white pixels on a
black background. I varied the width of the picture to look
for "patterns" that would show up at times. A fun, if a bit
crude, exercise. A DOS program with VESA graphics. Humans
can see (false) patterns in some random data.
Cheers,
Steve N.
Quote from: FORTRANS on February 24, 2025, 01:21:14 AMHi,
I wrote a program to display primes as white pixels on a
black background. I varied the width of the picture to look
for "patterns" that would show up at times. A fun, if a bit
crude, exercise. A DOS program with VESA graphics. Humans
can see (false) patterns in some random data.
Cheers,
Steve N.
Hi Steve. Interesting. I am sure that daydreamer would like to see that code, if it is still available. Magnus (daydreamer) has been experimenting with displaying the primes as a bitmap. Seems very similar to your idea, unless of course I misunderstood Magnus' discussion and intention regarding prime numbers and using bitmaps.
Magnus? What say you?
Quote from: zedd151 on February 24, 2025, 01:35:43 AMQuote from: FORTRANS on February 24, 2025, 01:21:14 AMHi,
I wrote a program to display primes as white pixels on a
black background. I varied the width of the picture to look
for "patterns" that would show up at times. A fun, if a bit
crude, exercise. A DOS program with VESA graphics. Humans
can see (false) patterns in some random data.
Cheers,
Steve N.
Hi Steve. Interesting. I am sure that daydreamer would like to see that code, if it is still available. Magnus (daydreamer) has been experimenting with displaying the primes as a bitmap. Seems very similar to your idea, unless of course I misunderstood Magnus' discussion and intention regarding prime numbers and using bitmaps.
Magnus? What say you?
here is 1 bit/pixel bitmap drawing/output I was going to use as starting point
512kb*8 pixels/byte and few bytes overhead its possible to store lots of primes
I had to fix the path for "ptexture.inc", and used "console assemble and link".
Well, at least its a start. The resulting bmp looks like a two lane highway, :tongue:
Now to implement this bitmap code in your prime numbers code for display. :biggrin:
Quote from: zedd151 on February 24, 2025, 04:15:38 AMWell, at least its a start. The resulting bmp looks like a two lane highway, :tongue:
After earthquake :biggrin:
Quote from: TimoVJL on February 24, 2025, 04:27:23 AMQuote from: zedd151 on February 24, 2025, 04:15:38 AMWell, at least its a start. The resulting bmp looks like a two lane highway, :tongue:
After earthquake :biggrin:
lol
I'm pretty sure that Magnus was just testing the drawing functions and bitmap creation code prior to using those in the (hopefully near) future, for his prime number code.
Quote from: zedd151 on February 24, 2025, 04:39:30 AMQuote from: TimoVJL on February 24, 2025, 04:27:23 AMQuote from: zedd151 on February 24, 2025, 04:15:38 AMWell, at least its a start. The resulting bmp looks like a two lane highway, :tongue:
After earthquake :biggrin:
lol
I'm pretty sure that Magnus was just testing the drawing functions and bitmap creation code prior to using those in the (hopefully near) future, for his prime number code.
its reusing code I developed from Dos 13h 16bit code drawing different road tiles ->32bit code writing to .bmps instead
its already have compressing from a byte buffer to bits = 1/8 smaller data in writebmp proc
2 gb memory =17 179 869 184 pixels
3.8 gb memory 32 641 751 449 pixels
Quote from: daydreamer on February 24, 2025, 06:12:47 AMits reusing code I developed from Dos 13h 16bit code drawing different road tiles ->32bit code writing to .bmps instead
Okay. :thumbsup:
Here's my version, a li'l console program. Just spits the prime #s out with no formatting (left as an exercise for the reader).
A little neater than some other examples, perhaps.
;============================================
; -- Sieve of Erastothenes --
;
;============================================
.nolist
include \masm32\include\masm32rt.inc
.list
;============================================
; Defines, structures, prototypes, etc.
;============================================
Sieve PROTO maxNum:DWORD, primeBuffPtr:DWORD
$primeMarker EQU -1 ;Marker to indicate a prime # in buffer.
$CRLF EQU <13, 10>
$tab EQU 9
;============================================
; HERE BE DATA
;============================================
.data
UsageMsg DB $CRLF, "Usage: sieveoferastothenes #", $CRLF
DB $tab, "where ""#"" is the maximum # to search for primes.", $CRLF, $CRLF, 0
;============================================
; UNINITIALIZED DATA
;============================================
.data?
HeapHandle HANDLE ?
PrimeBuffer DD ? ;Base address of heap-allocated buffer.
CmdLineBuffer DB 256 DUP(?)
;============================================
; CODE LIVES HERE
;============================================
.code
start: CALL WinMain
INVOKE ExitProcess, 0
;====================================================================
; Mainline proc
;====================================================================
WinMain PROC
LOCAL maxNum:DWORD, currNum:DWORD, numBuffer[16]:BYTE
; Get max. prime # from command line:
INVOKE GetCL, 1, OFFSET CmdLineBuffer ;Get arg[1] from command line.
CMP EAX, 1 ;See how many args on CL.
JE getnum
; No arg. given, so show "usage" message:
INVOKE StdOut, OFFSET UsageMsg
JMP exit99
getnum: INVOKE atodw, OFFSET CmdLineBuffer
MOV maxNum, EAX
; Allocate a buffer for primes:
CALL GetProcessHeap
MOV HeapHandle, EAX
INVOKE HeapAlloc, EAX, 0, maxNum
MOV PrimeBuffer, EAX
; Find those primes!
INVOKE Sieve, maxNum, PrimeBuffer
; Show those primes!
MOV EBX, PrimeBuffer
MOV currNum, 1
showlp: CMP BYTE PTR [EBX], 0 ;Next # in prime buffer.
JE skip ; Nope, skip it.
INVOKE dwtoa, currNum, ADDR numBuffer
INVOKE StdOut, ADDR numBuffer
MOV WORD PTR numBuffer, " " ;Put a space between #s.
INVOKE StdOut, ADDR numBuffer
skip: ADD currNum, 2
ADD EBX, 2 ;Skip all even #s.
MOV EAX, currNum
CMP EAX, maxNum
JBE showlp
INVOKE HeapFree, HeapHandle, 0, PrimeBuffer
exit99: RET
WinMain ENDP
;=========================================================================
; Sieve (maxNum, primeBuffPtr)
;
; Here's the Sieve of Erastothenes, a method of finding all prime #s in a
; given range.
;
; The buffer passed in and returned with all primes marked out starts at
; 1, not 0.
;
; Prime numbers in the buffer are marked with a value of -1 (0FFh).
;=========================================================================
Sieve PROC maxNum:DWORD, primeBuffPtr:DWORD
; Initialize prime buffer to all primes (mark with -1):
MOV ECX, maxNum
MOV EDX, primeBuffPtr
MOV AL, $primeMarker
initlp: MOV [EDX], AL
INC EDX
LOOP initlp
; Starting at #4, mark out all even #s as not prime:
MOV ECX, primeBuffPtr
MOV EDX, ECX
ADD ECX, maxNum ;Get our stopping point.
ADD EDX, 3 ;Point to #4 (buffer starts @ 1).
nxtevn: MOV BYTE PTR [EDX], 0 ;Mark as not prime.
ADD EDX, 2 ;Jump by 2s.
CMP EDX, ECX ;Continue until
JB nxtevn ; we're @ end o'buffer.
; Here's the Sieve code: starting @ #3, mark out all multiples:
MOV EDX, primeBuffPtr
MOV ECX, 3 ;ECX = current number (start @ 3).
MOV EAX, ECX ;EAX = # to add to create multiples.
multlp: ADD ECX, EAX ;Next multiple.
CMP ECX, maxNum ;Are we at the end of buffer?
JA nxtmul ; Yep, done with these multiples.
MOV BYTE PTR [EDX + ECX - 1], 0 ; Nope, mark out as not prime.
JMP multlp ;Next multiple.
; Finished a set of multiples--go to next set:
nxtmul: ADD EAX, 2 ;Skip over even #s.
CMP EAX, maxNum ;Are we @ the last #?
JAE done ; Yep, we be outta here.
MOV ECX, EAX ; Else process that #s multiples.
JMP multlp
done: RET
Sieve ENDP
END start
Seems a slight error in your version. '2' should be present as the only even number. '1' should not be there.
1
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101I replaced the " " (space) in your code with a single byte "0Dh" for carriage return for better printout.
Should be...
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
Ack. I forgot about 2!
Fixed it (problem was in display code, not the actual sieve code).
Now the display separator character is in an EQUate @ top of code, so easily changed.
One might want to write #s to a file instead.
Quote from: NoCforMe on February 24, 2025, 07:29:11 AMOne might want to write #s to a file instead.
SieveOfErastothenes 1000>out.txt
'1' shouldn't be there. Yes I know it does not sound logical, given it is only divisible by itself or 1. But that's the way it is.
Prime numbers to 100 (https://www.dreambox.com/math/skills/numbers/prime-numbers#:~:text=The%20prime%20numbers%20up%20to,%2C%2083%2C%2089%2C%2097.), plus many, many other sources.
You're correct, of course.
Will fix it later ...
Quote from: NoCforMe on February 24, 2025, 07:40:49 AMWill fix it later ...
Ok. Nice litte coding exercise though. :smiley:
Hi,
Quote from: zedd151 on February 24, 2025, 01:35:43 AMHi Steve. Interesting. I am sure that daydreamer would like to see that code, if it is still available.
Located the code. Sieve code; 16-bit and I hardly recognize it. Display code;
16-bit and VESA, mostly looks okay?. Varying line length/picture width code;
nothing. Save image code; nothing. Some executables if you can run DOS plus
VESA Modes 103, 105, or 107?
Regards,
Steve
Hi Steve. I only mentioned it because I thought that daydreamer (Magnus) might be interested in it. Not for me, I don't speak DOS, and certainly not VESA. I will let Magnus weigh in... he might want to see it. Thanks for digging through your archives though, Steve.
I would make one change to your original code
done1:
mov eax,curnumber
@10:
inc eax
cmp eax,arrsize
jae done2
cmp byte ptr [esi+eax],0
jz @10
mov curnumber,eax
jmp @b
done2:
You don't need to chek every number. If you've marked off all multiples of 2 there's no need to do the same for 4, 6 ...
With a bigger buffer it runs noticeably quicker.
Yes. In my sieve code, after marking out all the even #s I start at 3 to eliminate multiples as non-primes, and advance my current # by 2 to skip all the even #s.
The same logic goes for 3s. If you've marked off 3, 6, 9... then no need to do 9, 18, 27... since the 3 takes care of them.
You mark off multiples of the next unmarked number.
Quote from: sinsi on February 24, 2025, 11:14:18 AMYou don't need to chek every number. If you've marked off all multiples of 2 there's no need to do the same for 4, 6 ...
With a bigger buffer it runs noticeably quicker.
okay. :smiley: I *might* revisit the code at some point. But I am not young anymore. Time is something I do not have an abundance of, and I have many other projects that need to get finished, and fully working. This code at least, already does exactly what it is intended to do. Now if you were to tell me that the results contain errors, or the program crashes, then most likely I would take care of that ASAP. :smiley:
You can think of my code as a starting point, if you or anyone else would like to optimize it further, I would not complain. :biggrin:
Quote from: zedd151 on February 24, 2025, 01:05:55 PMNow if you were to tell me that the results contain errors
I can't count that high :badgrin:
Quote from: sinsi on February 24, 2025, 01:36:56 PMQuote from: zedd151 on February 24, 2025, 01:05:55 PMNow if you were to tell me that the results contain errors
I can't count that high :badgrin:
Fair enough. :biggrin:
Quote from: zedd151 on February 24, 2025, 07:30:26 AMQuote from: NoCforMe on February 24, 2025, 07:29:11 AMOne might want to write #s to a file instead.
SieveOfErastothenes 1000>out.txt
'1' shouldn't be there. Yes I know it does not sound logical, given it is only divisible by itself or 1. But that's the way it is.
Prime numbers to 100 (https://www.dreambox.com/math/skills/numbers/prime-numbers#:~:text=The%20prime%20numbers%20up%20to,%2C%2083%2C%2089%2C%2097.), plus many, many other sources.
I have a primes.inc file with all primes between 0-65536 ,using DW in my 128 bit random generator thread
https://masm32.com/board/index.php?topic=7938.msg103022#msg103022
So you could include it into your program and cmp if its correct
@Steve I want to see your code ,its probably possible to port to 32 bit ,output BMP
Sinsi ,nocforme
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Look at animated gif and see in which order it multiplies to understand its mul 2,3,5,7,11,13...
The Sieve of Eratosthenes (https://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html)
with example in C language.
Quote from: TimoVJL on February 24, 2025, 10:18:54 PMThe Sieve of Eratosthenes
with example in C language.
Thanks Timo for you contribution. Seems to be an optimized version. :biggrin:
Did you make any further changes to the code, or is it code directly copied from the attachment in your linked paper? Sounds like a good candidate for porting to assembly. Further enhancements/optimizations may be possible with asm. :biggrin: Any takers? Sinsi? Magnus? Jochen? David? Anyone? Myself, I am busy with other projects.
"prime_sieve.c" from your attachment compiles fine with
gcc. I have no experience with other compilers.
All those
extraneous .pp* files are
not needed. :biggrin:
The resulting executable runs just fine. :thumbsup:
I just made a Pelles C project for that code from that site and nothing else from me.
Quote from: TimoVJL on February 25, 2025, 02:06:28 AMI just made a Pelles C project for that code from that site and nothing else from me.
Okay, thats fine. I wasn't sure, so I asked. Nice example regardless. Thanks. :smiley:
New version. Improved sieve (mo' faster!), better formatting of output (16 numbers per line), shows correct primes (not 1!). Fully-commented, of course.
Glad to have inspired you, NoCforMe. I'll take a gander at your latest Sieve of *Eratosthenes (https://en.m.wikipedia.org/wiki/Eratosthenes) code when I am back at my computer. :smiley:
A short time later:
328 milliseconds for prime numbers to 1,000,000. Similar timings to my version posted above.
The output looks good, no apparent errors in the range 0-1,000,000.
Quote from: zedd151 on February 25, 2025, 06:47:59 AM328 milliseconds for prime numbers to 1,000,000. Similar timings to my version posted above.
Does your timing include the display of those #s? or did you just time the sieve code itself?
Quote from: NoCforMe on February 25, 2025, 07:39:09 AMQuote from: zedd151 on February 25, 2025, 06:47:59 AM328 milliseconds for prime numbers to 1,000,000. Similar timings to my version posted above.
Does your timing include the display of those #s? or did you just time the sieve code itself?
The whole shebang.
start:
invoke GetTickCount
mov time1, eax
CALL WinMain
invoke GetTickCount
sub eax, time1
INVOKE StdOut, str$(eax)
INVOKE ExitProcess, 0
For longer, time consuming code it works okay, to test relative difference between one program or algorithm against another, or after making changes to the code to test whether the changes yields a speed improvement or not.
For much shorter pieces of code, looping multiple iterations (thousands to millions) are needed (use caution though, to not give erroneous algo results or timing errors), or other timing methods that may be more appropriate like jj's nano timer, or other methods using microsecond timers. :smiley:
...
I had to come back and edit the code snippet to what I actually used to get the timing of your code...
I'd rather see timings for just the actual sieve code.
The display code will take f-o-r-e-v-e-r.
For my program, just call Sieve() multiple times in a loop and time that whole shebang. Not hard to do.
CALL GetTickCount
MOV startTime, EAX
MOV ECX, [# times to call Sieve() ]
@@: PUSH ECX
INVOKE Sieve, maxNum, PrimeBuffer
POP ECX
LOOP @B
CALL GetTickCount
SUB EAX, startTime
; display total time in EAX
4,829 milliseconds for 1000 repititions for prime numbers from 0-1000000. So 4.8 microseconds per iteration. Seems fast enough.
By the way, it registers 0 MS running the function only once. :azn:
Here using the 'repeat' macro to run 1000 iterations of the Sieve function for the timing.
; Find those primes!
invoke GetTickCount
mov time1, eax
repeat 1000
INVOKE Sieve, maxNum, PrimeBuffer
endm
invoke GetTickCount
sub eax, time1
invoke MessageBox, 0, str$(eax), 0, 0
The modified code attached, including file 'run.bat'
run.bat:
SieveOfErastothenes 1000000>out.txt
pauseI prefer using batch files than typing at the command prompt. I didn't grow up using DOS. :biggrin:
So what's the timing of your code?
BTW, you don't have to use INVOKE with GetTickCount(), since it takes no parameters. A simple CALL will do.
Quote from: zedd151 on February 25, 2025, 08:41:12 AMI prefer using batch files than typing at the command prompt. I didn't grow up using DOS. :biggrin:
Well, then you have no idea what kind of fun you missed!
But really: not trying to convince you to do something that goes against your grain, but it's actually easier in the long run having a command window open without having to continually get new ones. Of course, I use a different command processor (4DOS, been using it for decades, still works great on Windows 7) that's a bit smarter than plain old "cmd".
But the DOS commands are pretty basic and easy to remember: of course, there are your existing batch files that you simply invoke by typing their name. Then there's
COPY,
DEL, etc. for files. And the command window keeps a history of previous commands executed, so you can look back and see which assembler errors are still there, f'rinstance.
Even "cmd" has a HELP command.
You might try it some day when you have time and maybe are really bored ...
Quote from: NoCforMe on February 25, 2025, 10:51:11 AMSo what's the timing of your code?
It took me a minute to procedurize that part of the code....
11,487 milliseconds for 1,000 iterations for primes 0-1,000,000... Yikes! almost takes three times longer than your latest. :rolleyes:
Bbbutt, bbbut, but wait a minute. I thought you didn't give two hoots how fast code is, or could be... :greensml:
QuoteBTW, you don't have to use INVOKE with GetTickCount(), since it takes no parameters. A simple CALL will do.
it's muscle memory that forces me to always write 'invoke'. That's my story and I'm sticking to it. :biggrin:
I 'invoke' and 'call' --- ALL CAPS IS SO 1980's...
... I had some weird formatting bugs when posting originally. I musta accidentally hit some formatting buttons...
Quote from: zedd151 on February 25, 2025, 11:22:35 AMI 'invoke' and 'call' --- ALL CAPS IS SO 1980's...
Ackshooly, it's more like 1960s. Like those programs that ran the Apollo mission.
Quote from: zedd151 on February 25, 2025, 11:22:35 AM11,487 milliseconds for 1,000 iterations for primes 0-1,000,000... Yikes! almost takes three times longer than your latest. :rolleyes:
Bbbutt, bbbut, but wait a minute. I thought you didn't give two hoots how fast code is, or could be... :greensml:
Normally I don't. But in this case I get to say:
Nya nya nya nya: My code's faster than your code!
(If you care, you need to skip computing multiples of numbers that are already taken out as primes, as sinsi suggested upthread. Then yours will be as fast as mine.)
Quote from: NoCforMe on February 25, 2025, 11:58:31 AMQuote from: zedd151 on February 25, 2025, 11:22:35 AMBbbutt, bbbut, but wait a minute. I thought you didn't give two hoots how fast code is, or could be... :greensml:
Normally I don't. But in this case I get to say:
Nya nya nya nya: My code's faster than your code!
When I wrote that code, I was more concerned about accuracy and simplicity than speed. If you give me a coupla days, I'll make mine faster than yours. :badgrin:
Just kidding, mine still serves a purpose, as is.
Just my five cents :smiley:
; Sieve of Eratosthenes in MASM64
include \masm64\include64\masm64rt.inc
.data
n dq 1000000 ; Limit for prime numbers
sqrt_n dq 3e8h ; Square root of n
sieve db 1000000 dup(1) ; Sieve array, initialized to 1 (true)
.code
align 16
db 3 dup(90h)
entry_point proc
; Calculate sqrt(n)
; fild n
; fsqrt
; fistp sqrt_n
; Initialize registers
mov rdx, 2 ; Start from the first prime number
lea r8, sieve
mov r9, n ; r9 = Limit for prime numbers
@loop:
cmp byte ptr [r8+rdx],1 ; Check if sieve[rdx] is 1 (true)
mov rax, rdx
jne @next
nop
imul rax, rax
nop
@@:
mov byte ptr [r8+rax], 0 ; Mark multiples of rax as 0 (false) Set sieve[rax] to 0
add rax, rdx
cmp rax, r9 ; r9 = Limit for prime numbers
jb @b
@next:
add rdx, 1
cmp rdx, 3e8h ; sqrt_n = 3e8h
jbe @loop
xor rcx, rcx
call ExitProcess ; Exit the program
entry_point endp
end
Quote from: ognil on February 25, 2025, 01:06:44 PMJust my five cents :smiley:
:biggrin:
32 bit conversion below. I hope that you don't mind.
After a couple changes, the prime listing is 100% accurate. :thumbsup:
I have converted ognils 64 bit code to 32 bit.
And I made a change by preinitialising the .data section array so all even numbers are pre-initialized to zero, and marked 1 as non prime, and 2 as prime manually in the code..
Added function to print the prime numbers. Use Console Assemble & Link.
; Sieve of Eratosthenes - ognil
; 32 bit conversion by zedd151 - also added code to print results, and a couple other adjustments
include \masm32\include\masm32rt.inc
.data
n dd 1000000 ; Limit for prime numbers
sqrt_n dd 1000 ; Square root of n
; array is now 250000 dwords, but will use it bytewise.
; we mark initialize all even numbers to zero.
sieve dd 250000 dup(01000100h) ; Sieve array, initialized to 00, 01, 00, 01, etc.
time1 dd 0
.code
PrimeSieve proc
push ebx
push edi
xor edx, edx ; set edx to 2
inc edx ; doing it this way aligns both loops to 4
inc edx ; Start from the first prime number
lea edi, sieve
mov byte ptr [edi+1], 0 ; mark 1 as not prime
mov byte ptr [edi+2], 1 ; mark 2 as prime
mov ebx, n ; ebx = Limit for prime numbers
nop ; padding to align loops to 4 bytes
nop
@loop:
cmp byte ptr [edi+edx],1 ; Check if sieve[edx] is 1 (true)
mov eax, edx
jne @next
nop
imul eax, eax
@@:
mov byte ptr [edi+eax], 0 ; Mark multiples of eax as 0 (false) Set sieve[eax] to 0
add eax, edx
cmp eax, ebx ; ebx = Limit for prime numbers
jb @b
@next:
add edx, 1
cmp edx, 3e8h ; sqrt_n = 3e8h
jbe @loop
pop edi
pop ebx
ret
PrimeSieve endp
PrintPrimes proc
push ebx
push edi
lea edi, sieve
xor ebx, ebx
@@:
cmp byte ptr [edi+ebx], 0
jz noprint
print str$(ebx), 13, 10
noprint:
inc ebx
cmp ebx, n
jnz @b
pop edi
pop ebx
ret
PrintPrimes endp
start:
CALL PrimeSieve ; just for NoCforMe!
call PrintPrimes ; :)
push 0
call ExitProcess ; Exit the program
end start
1219 milliseconds for 1000 iterations for range 0-1000000
1.2 microseconds to get primes from 0-1000000. Very fast indeed.