MAYBE

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict Trs:
  { gt(s(x), s(y)) -> gt(x, y)
  , gt(s(x), 0()) -> true()
  , gt(0(), y) -> false()
  , divides(x, y) -> div(x, y, y)
  , div(s(x), s(y), z) -> div(x, y, z)
  , div(s(x), 0(), s(z)) -> div(s(x), s(z), s(z))
  , div(0(), s(x), z) -> false()
  , div(0(), 0(), z) -> true()
  , prime(x) -> test(x, s(s(0())))
  , test(x, y) -> if1(gt(x, y), x, y)
  , if1(true(), x, y) -> if2(divides(x, y), x, y)
  , if1(false(), x, y) -> true()
  , if2(true(), x, y) -> false()
  , if2(false(), x, y) -> test(x, s(y)) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

The input cannot be shown compatible

Arrrr..