### Demo-Programm für MIPS für die Vorlesung ###
###        "Grundlagen der Informatik"       ###
###               Jörg Roth                  ###
###
### primetest: Teste, ob x eine Primzahl ist
### Achtung: der Algorithmus ist nicht sehr effizient, denn
### es wird jede ungerade Zahl zwischen 3 und x/2 getestet.
### Gerade Zahlen werden separat ausgefiltert (mit Ausnahme 2)
###
### $s0:   Eingabe x
### $s1:   Ergebnis (1: Primzahl, 0: keine Primzahl)
### $s2:   Konstante 2
### $s3:   Hilfsregister, z.B: x/2 für den Schleifentest
### $s4:   Schleifenregister: durch diese Zahl wird x geteilt
### $s5:   Hilfsregister, z.B.: Teilungsrest der Division und Vergleichsergebnis für Schleifentest


	.text
main:
     li $v0, 5               # Eingabe einlesen
     syscall
     or $s0, $zero, $v0      # $s0 := Eingabe

### Hier beginnt die Berechnung ###

     li $s1, 1               # Ergebnis =1 (ist Primzahl) vorbelegen
     li $s2, 2               # Konstante 2 wird mehrfach benötigt
     beq $s0, $s2, end       # Vergleich mit 2 => Primzahl
     and $s3, $s0, 1         # Alle Bits bis auf das letzte ausmaskieren
     beq $s3, $zero, noprime # Letztes Bit war 0, also gerade => keine Primzahl

     ### An dieser Stelle muss es sich um eine ungerade Zahl handeln ###

     beq $s0,$s1, noprime    # Vergleich mit 1 => keine Primzahl
     srl $s3, $s0,1          # 1 Mal Shiften, d.h. durch 2 teilen
     li $s4, 3               # 3 ist die erste Zahl durch die geteilt wird
loop:
     sltu $s5,$s4,$s3        # $s4=0 wenn $s4>=$s3, 
     beq $s5,$zero,end       # d.h. wir haben x/2 erreicht => Primzahl
     div $s0,$s4             # Es wird auf Teilbarkeit geprüft
     mfhi $s5                # $s5 ist Teilerrest
     beq $s5,$zero,noprime   # Der Teilungsrest war 0 => keine Primzahl
     addi $s4,$s4,2          # Die Schleifenvariable wird um zwei erhöht
     j loop                  # Erneut testen
     

noprime:
     li $s1, 0               # Ergebnis =0 (keine Primzahl)
end:

### Hier endet die Berechnung ###

     li $v0, 1               # Resultat ausgeben
     or $a0, $zero, $s1      # in $s1 stand das Ergebnis
     syscall