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())

linear polynomial interpretations on N:

  prime_A(x1) = 2
  prime#_A(x1) = 5
  0_A = 1
  0#_A = 1
  false_A = 0
  false#_A = 0
  s_A(x1) = 1
  s#_A(x1) = 4
  prime1_A(x1,x2) = x1 + 1
  prime1#_A(x1,x2) = x1 + 3
  true_A = 0
  true#_A = 0
  and_A(x1,x2) = 0
  and#_A(x1,x2) = x2
  not_A(x1) = 1
  not#_A(x1) = 0
  divp_A(x1,x2) = x1 + x2
  divp#_A(x1,x2) = x2 + 2
  =_A(x1,x2) = 0
  =#_A(x1,x2) = 0
  rem_A(x1,x2) = x2 + 1
  rem#_A(x1,x2) = 0

precedence:

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