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())}
 RPO Product:
  Quasi-Precedence:
  prime1 > divp, 
  prime > prime1
  empty
  
  Qed


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())}
 Cdiprover:
  Interpretation class: quasisimplemixed
  Complexity bound: POLYTIME COMPUTABLE IF RPO-TERMINATING
  rem(X12, X11) = + 1*X11 + 1*X12 + 1
  =(X10, X9) = + 1*X9 + 1*X10 + 1
  divp(X8, X7) = + 0*X8^2 + 0*X7^2 + 1*X8 + 2 + 1*X7 + 0*X7*X8
  not(X6) = + 1*X6 + 3
  and(X5, X4) = + 1*X4 + 1*X5 + 1
  true = + 0
  prime1(X3, X2) = + 0*X3^2 + 1*X2^2 + 2*X3 + 0 + 1*X2 + 1*X2*X3
  s(X1) = + 1*X1 + 3
  0 = + 0
  prime(X0) = + 2*X0^2 + 0 + 1*X0
  false = + 0
  
  Qed