#Copyright 2021 by John Bowman
#Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), 
#to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
#and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
#The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
#THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
#FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
#WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

#This program computes the first 100 prime numbers

#Developed using MARS 4.5 MIPS Assembler and Runtime Simulator

.data
  primes: .asciiz "\nThe first 100 prime numbers are: "
  space: .asciiz " "
  
.text
  li $v0, 4
  la $a0, primes
  syscall
  
  addi $t0, $zero, 0 #Initialize looping variables
  addi $t1, $zero, 100 #Specifies limit of prime numbers
  addi $t2, $zero, 2 #Start at first prime
  addi $t4, $zero, 2 #Divide every number by $t4 to test for primality
  
  beq $t2, 2, isPrime #Special case for #2
  
  startLoop:
   beq $t0, $t1, exitLoop #Exit when maximum number of primes reached

   j innerLoop
   
   inLoop:
     addi $t2, $t2, 1 
   
   j startLoop
  
  innerLoop:
    addi $t4, $zero, 2 #Start with division by two and increment to test for primality
    move $t5, $t2
    
    innerBranch:
      divu $t5, $t4
      mfhi $t3 #Fetch remainder
      beqz $t3, inLoop #KEY operation. Terminate if remainder equals zero.
     
      addi $t4,$t4,1
      beq $t4, $t5, isPrime #Loop is finished and no tested values equaled zero. Number is prime!
      j innerBranch #Iterate the loop
    
  exitLoop:
     #Terminate program
     li $v0, 10
     syscall
  
  isPrime:
     #Increment count of prime numbers found
     addi $t0, $t0, 1
     
     #Print prime number
     li $v0, 1
     la $a0, ($t2)
     syscall
     
     
     #Print blank space
     li $v0, 4
     la $a0, space
     syscall
     
     j inLoop