;; read in an integer n and write 1 if n is prime, or write 0 if not

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Def: n is prime iff n > 1 and n is not divisible by and d, where 1 < d < n.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Pseudocode follows.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; read n
;; if n < 1 then {
;;     isPrime <- 0
;; } else {
;;     isPrime <- 1
;;     for (d = 2; d < n; d+) {
;;         if (n % d == 0) {
;;             isPrime <- 0
;;             break;
;;         }
;;     }
;; }
;;
;; write isPrime
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    allocate-registers n, one, zero, test, result, notPrime, prime, d, isPrime, loop, done, cont, isAPrime

    li loop loopL
    li done doneL
    li prime primeL
    li notPrime notPrimeL
    li isAPrime isAPrimeL

    li one 1
    li zero 0

    read n
    li cont doneL
    j isAPrime
doneL:
    write isPrime
    halt

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; isAPrime starts here ;;;;;;;;;;;;;;;;;;;;;;;;;;
;; n - input register
;; isPrime - output register
;; cont - continuation register
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

isAPrimeL:
    sgt test n one 

    jeqz test, notPrime  
    li d 2
loopL:
    sne test, d, n
    jeqz test, prime    

    rem result, n, d
    sne test, result, zero
    jeqz test, notPrime
    add  d, d, one
   
    j loop

notPrimeL:
    li isPrime,  0
    j cont
primeL:
    li isPrime, 1
    j cont