YES(?,O(n^1))
TRS:
 {
  filter(cons X, 0(), M) -> cons 0(),
  filter(cons X, s N, M) -> cons X,
          sieve cons 0() -> cons 0(),
          sieve cons s N -> cons s N,
                  nats N -> cons N,
               zprimes() -> sieve nats s s 0()
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
    filter(cons X, 0(), M) -> cons 0(),
    filter(cons X, s N, M) -> cons X,
            sieve cons 0() -> cons 0(),
            sieve cons s N -> cons s N,
                    nats N -> cons N,
                 zprimes() -> sieve nats s s 0()
   }
  Natural interpretation:
   Strict:
    {
     filter(cons X, 0(), M) -> cons 0(),
     filter(cons X, s N, M) -> cons X,
             sieve cons 0() -> cons 0(),
             sieve cons s N -> cons s N,
                     nats N -> cons N,
                  zprimes() -> sieve nats s s 0()
    }
   Weak:
    {}
   Interpretation class: stronglylinear
   [zprimes] = + 7
   [nats](X0) = + 1*X0 + 5
   [sieve](X0) = + 1*X0 + 1
   [s](X0) = + 1*X0 + 0
   [filter](X2, X1, X0) = + 1*X0 + 1*X1 + 1*X2 + 4
   [0] = + 0
   [cons](X0) = + 1*X0 + 0
   
   Qed