This version is written in Intel assembly language, specifically that for the standard desk top PC. It will probably run under Windows, but I have tested it only on the Linux operating system. You can compile it just like it was a C program, using the cc command. All assembly languages are pretty much the same, but the Intel architecture poses some challenges. Specifically, there are only four general purpose regisers, which just isn't enough. In addition there is the calling convention that states that the caller must preserve all register values.
This program compiles and runs under the standard Linux implementation of the cc command. This is, of course, gcc.
/*////////////////////////////////////////////////////////
// Name: Peter M. Maurer
// Program: Sieve of Eratosthenes
// Due: Never
// Language: i386 assembler (GNU)
////////////////////////////////////////////////////////*/
.text
.globl main
main:
/* standard prolog */
pushl %ebp
movl %esp, %ebp
subl $8, %esp
andl $-16, %esp
movl $1000,%ebx
leal Candidates,%eax
init:
/* everything is potentially prime until proven otherwise */
movl $1,(%eax)
addl $4,%eax
decl %ebx
jnz init
/* Neither 1 nor 0 is prime, so flag them off */
movl $0,Candidates
movl $0,Candidates+4
/* start the sieve with the integer 0 */
leal Candidates,%eax
movl $0,%ebx
OuterWhile:
/* advance to the next un-crossed out number. */
/* this number must be a prime */
InnerWhile1:
cmpl $1000,%ebx
jge EndOuter
cmpl $0,(%eax)
jne EndInner1
incl %ebx
addl $4,%eax
jmp InnerWhile1
EndInner1:
/* cross out all multiples of the prime, starting with 2*p. */
movl %eax,%ecx
movl %ebx,%edx
Innerwhile2:
addl %ebx,%edx
cmpl $1000,%edx
jge EndInner2
/* out of registers */
addl %ebx,%ecx
addl %ebx,%ecx
addl %ebx,%ecx
addl %ebx,%ecx
movl $0,(%ecx)
jmp Innerwhile2
EndInner2:
/* advance to the next candidate */
incl %ebx
addl $4,%eax
jmp OuterWhile
EndOuter:
/* all uncrossed-out numbers are prime (and only those numbers) */
/* print all primes */
leal Candidates,%eax
movl $0,%ebx
PrintLoop:
cmpl $1000,%ebx
jge EndPrint
cmpl $0,(%eax)
je NoPrint
movl %eax,i
movl %ebx,j
pushl %ebx
pushl $Msg
pushl stdout
call fprintf
addl $12,%esp
movl i,%eax
movl j,%ebx
NoPrint:
incl %ebx
addl $4,%eax
jmp PrintLoop
EndPrint:
/* standard epilog */
leave
ret
.data
Msg: .string "%d is prime\n"
i: .long 0
j: .long 0
/* define the sieve data structure */
.align 8
Candidates:
.long 0,0,0,0,0,0,0,0,0,0
/* the above line is repeated 100 times */