procedure main(A)
   every n := !A do write(n," is ",(mrp(n,5),"probably prime")|"composite")
end

procedure mrp(n, k)
    if n = 2 then return ""
    if n%2 = 0 then fail
    nm1 := decompose(n-1)
    s := nm1[1]
    d := nm1[2]
    every !k do {
        a := ?(n-2)+1
        x := (a^d)%n
        if x = (1|(n-1)) then next
        every !(s-1) do {
            x := (x*x)%n
            if x = 1 then fail
            if x = (n-1) then break next
            }
        fail
        }
    return ""
end

procedure decompose(nm1)
    s := 1
    d := nm1
    while d%2 = 0 do {
        d /:= 2
        s +:= 1
        }
    return [s,d]
end