YES

TRS:

  prime(0()) -> false()
  prime(s(0())) -> false()
  prime(s(s(x))) -> prime1(s(s(x)),s(x))
  prime1(x,0()) -> false()
  prime1(x,s(0())) -> true()
  prime1(x,s(s(y))) -> and(not(divp(s(s(y)),x)),prime1(x,s(y)))
  divp(x,y) -> =(rem(x,y),0())

max/plus interpretations on N:

  prime_A(x1) = max{0, x1}
  prime#_A(x1) = max{0, x1}
  0_A = 0
  0#_A = 0
  false_A = 0
  false#_A = 0
  s_A(x1) = max{0, x1}
  s#_A(x1) = max{0, x1}
  prime1_A(x1,x2) = max{0, x1, x2}
  prime1#_A(x1,x2) = max{0, x1, x2}
  true_A = 0
  true#_A = 0
  and_A(x1,x2) = max{0, x1, x2}
  and#_A(x1,x2) = max{0, x1, x2}
  not_A(x1) = max{0, x1}
  not#_A(x1) = max{0, x1}
  divp_A(x1,x2) = max{0, x1, x2}
  divp#_A(x1,x2) = max{0, x1, x2}
  =_A(x1,x2) = max{0, x1, x2}
  =#_A(x1,x2) = max{0, x1, x2}
  rem_A(x1,x2) = max{0, x1, x2}
  rem#_A(x1,x2) = max{0, x1, x2}

precedence:

  s > prime > prime1 > 0 = and = not = divp > false = true = = = rem