################################################################################
# MIPS assembly implementation of the Sieve of Eratosthenes to find prime #
# numbers between 2 and a specified integer #
################################################################################
# Optimized for the standard terminal size of 80 columns x 24 rows #
################################################################################
.data # the data segment to store global data
space: .asciiz " " # whitespace to separate prime numbers
.text # the text segment to store instructions
.globl main # define main to be a global label
main: li $s0, 0x00000000 # initialize $s0 with zeros
li $s1, 0x11111111 # initialize $s1 with ones
li $t9, 200 # find prime numbers from 2 to $t9
add $s2, $sp, 0 # backup bottom of stack address in $s2
li $t0, 2 # set counter variable to 2
init: sw $s1, ($sp) # write ones to the stackpointer's address
add $t0, $t0, 1 # increment counter variable
sub $sp, $sp, 4 # subtract 4 bytes from stackpointer (push)
ble $t0, $t9, init # take loop while $t0 <= $t9
li $t0, 1 # reset counter variable to 1
outer: add $t0, $t0, 1 # increment counter variable (start at 2)
mul $t1, $t0, $t0 # multiply $t0 with itself and save to $t1
bgt $t1, $t9, print # start printing prime numbers when $t1 > $t9
check: add $t2, $s2, 0 # save the bottom of stack address to $t2
mul $t3, $t0, 4 # calculate the number of bytes to jump over
sub $t2, $t2, $t3 # subtract them from bottom of stack address
add $t2, $t2, 8 # add 2 words - we started counting at 2!
lw $t3, ($t2) # load the content into $t3
beq $t3, $s0, outer # only 0's? go back to the outer loop
inner: add $t2, $s2, 0 # save the bottom of stack address to $t2
mul $t3, $t1, 4 # calculate the number of bytes to jump over
sub $t2, $t2, $t3 # subtract them from bottom of stack address
add $t2, $t2, 8 # add 2 words - we started counting at 2!
sw $s0, ($t2) # store 0's -> it's not a prime number!
add $t1, $t1, $t0 # do this for every multiple of $t0
bgt $t1, $t9, outer # every multiple done? go back to outer loop
j inner # some multiples left? go back to inner loop
print: li $t0, 1 # reset counter variable to 1
count: add $t0, $t0, 1 # increment counter variable (start at 2)
bgt $t0, $t9, exit # make sure to exit when all numbers are done
add $t2, $s2, 0 # save the bottom of stack address to $t2
mul $t3, $t0, 4 # calculate the number of bytes to jump over
sub $t2, $t2, $t3 # subtract them from bottom of stack address
add $t2, $t2, 8 # add 2 words - we started counting at 2!
lw $t3, ($t2) # load the content into $t3
beq $t3, $s0, count # only 0's? go back to count loop
add $t3, $s2, 0 # save the bottom of stack address to $t3
sub $t3, $t3, $t2 # substract higher from lower address (= bytes)
div $t3, $t3, 4 # divide by 4 (bytes) = distance in words
add $t3, $t3, 2 # add 2 (words) = the final prime number!
li $v0, 1 # system code to print integer
add $a0, $t3, 0 # the argument will be our prime number in $t3
syscall # print it!
li $v0, 4 # system code to print string
la $a0, space # the argument will be a whitespace
syscall # print it!
ble $t0, $t9, count # take loop while $t0 <= $t9
exit: jr $ra # exit! we're done!