Runtime Complexity TRS:
The TRS R consists of the following rules:

primes → sieve(from(s(s(0))))
from(X) → cons(X, n__from(n__s(X)))
head(cons(X, Y)) → X
tail(cons(X, Y)) → activate(Y)
if(true, X, Y) → activate(X)
if(false, X, Y) → activate(Y)
filter(s(s(X)), cons(Y, Z)) → if(divides(s(s(X)), Y), n__filter(n__s(n__s(X)), activate(Z)), n__cons(Y, n__filter(X, n__sieve(Y))))
sieve(cons(X, Y)) → cons(X, n__filter(X, n__sieve(activate(Y))))
from(X) → n__from(X)
s(X) → n__s(X)
filter(X1, X2) → n__filter(X1, X2)
cons(X1, X2) → n__cons(X1, X2)
sieve(X) → n__sieve(X)
activate(n__from(X)) → from(activate(X))
activate(n__s(X)) → s(activate(X))
activate(n__filter(X1, X2)) → filter(activate(X1), activate(X2))
activate(n__cons(X1, X2)) → cons(activate(X1), X2)
activate(n__sieve(X)) → sieve(activate(X))
activate(X) → X

Rewrite Strategy: INNERMOST

Renamed function symbols to avoid clashes with predefined symbol.

Runtime Complexity TRS:
The TRS R consists of the following rules:

primes' → sieve'(from'(s'(s'(0'))))
from'(X) → cons'(X, n__from'(n__s'(X)))
head'(cons'(X, Y)) → X
tail'(cons'(X, Y)) → activate'(Y)
if'(true', X, Y) → activate'(X)
if'(false', X, Y) → activate'(Y)
filter'(s'(s'(X)), cons'(Y, Z)) → if'(divides'(s'(s'(X)), Y), n__filter'(n__s'(n__s'(X)), activate'(Z)), n__cons'(Y, n__filter'(X, n__sieve'(Y))))
sieve'(cons'(X, Y)) → cons'(X, n__filter'(X, n__sieve'(activate'(Y))))
from'(X) → n__from'(X)
s'(X) → n__s'(X)
filter'(X1, X2) → n__filter'(X1, X2)
cons'(X1, X2) → n__cons'(X1, X2)
sieve'(X) → n__sieve'(X)
activate'(n__from'(X)) → from'(activate'(X))
activate'(n__s'(X)) → s'(activate'(X))
activate'(n__filter'(X1, X2)) → filter'(activate'(X1), activate'(X2))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__sieve'(X)) → sieve'(activate'(X))
activate'(X) → X

Rewrite Strategy: INNERMOST

Sliced the following arguments:
divides'/1

Runtime Complexity TRS:
The TRS R consists of the following rules:

primes' → sieve'(from'(s'(s'(0'))))
from'(X) → cons'(X, n__from'(n__s'(X)))
head'(cons'(X, Y)) → X
tail'(cons'(X, Y)) → activate'(Y)
if'(true', X, Y) → activate'(X)
if'(false', X, Y) → activate'(Y)
filter'(s'(s'(X)), cons'(Y, Z)) → if'(divides'(s'(s'(X))), n__filter'(n__s'(n__s'(X)), activate'(Z)), n__cons'(Y, n__filter'(X, n__sieve'(Y))))
sieve'(cons'(X, Y)) → cons'(X, n__filter'(X, n__sieve'(activate'(Y))))
from'(X) → n__from'(X)
s'(X) → n__s'(X)
filter'(X1, X2) → n__filter'(X1, X2)
cons'(X1, X2) → n__cons'(X1, X2)
sieve'(X) → n__sieve'(X)
activate'(n__from'(X)) → from'(activate'(X))
activate'(n__s'(X)) → s'(activate'(X))
activate'(n__filter'(X1, X2)) → filter'(activate'(X1), activate'(X2))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__sieve'(X)) → sieve'(activate'(X))
activate'(X) → X

Rewrite Strategy: INNERMOST

Infered types.

Rules:
primes' → sieve'(from'(s'(s'(0'))))
from'(X) → cons'(X, n__from'(n__s'(X)))
head'(cons'(X, Y)) → X
tail'(cons'(X, Y)) → activate'(Y)
if'(true', X, Y) → activate'(X)
if'(false', X, Y) → activate'(Y)
filter'(s'(s'(X)), cons'(Y, Z)) → if'(divides'(s'(s'(X))), n__filter'(n__s'(n__s'(X)), activate'(Z)), n__cons'(Y, n__filter'(X, n__sieve'(Y))))
sieve'(cons'(X, Y)) → cons'(X, n__filter'(X, n__sieve'(activate'(Y))))
from'(X) → n__from'(X)
s'(X) → n__s'(X)
filter'(X1, X2) → n__filter'(X1, X2)
cons'(X1, X2) → n__cons'(X1, X2)
sieve'(X) → n__sieve'(X)
activate'(n__from'(X)) → from'(activate'(X))
activate'(n__s'(X)) → s'(activate'(X))
activate'(n__filter'(X1, X2)) → filter'(activate'(X1), activate'(X2))
activate'(n__cons'(X1, X2)) → cons'(activate'(X1), X2)
activate'(n__sieve'(X)) → sieve'(activate'(X))
activate'(X) → X

Types:
primes' :: 0':n__s':n__from':n__filter':n__sieve':n__cons'
sieve' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
from' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
s' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
0' :: 0':n__s':n__from':n__filter':n__sieve':n__cons'
cons' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
n__from' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
n__s' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
head' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
tail' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
activate' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
if' :: true':false':divides' → 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
true' :: true':false':divides'
false' :: true':false':divides'
filter' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
divides' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → true':false':divides'
n__filter' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
n__cons' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
n__sieve' :: 0':n__s':n__from':n__filter':n__sieve':n__cons' → 0':n__s':n__from':n__filter':n__sieve':n__cons'
_hole_0':n__s':n__from':n__filter':n__sieve':n__cons'1 :: 0':n__s':n__from':n__filter':n__sieve':n__cons'
_hole_true':false':divides'2 :: true':false':divides'
_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3 :: Nat → 0':n__s':n__from':n__filter':n__sieve':n__cons'

Heuristically decided to analyse the following defined symbols:
sieve', activate'

They will be analysed ascendingly in the following order:
sieve' = activate'

Generator Equations:
_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(0) ⇔ 0'
_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(x, 1)) ⇔ n__from'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(x))

The following defined symbols remain to be analysed:
activate', sieve'

They will be analysed ascendingly in the following order:
sieve' = activate'

Proved the following rewrite lemma:
activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, _n5))) → _*4, rt ∈ Ω(_n5)

Induction Base:
activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, 0)))

Induction Step:
activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, +(_$n6, 1)))) →_R^Ω(1)
from'(activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, _$n6)))) →_IH
from'(_*4)

We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

Lemmas:
activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, _n5))) → _*4, rt ∈ Ω(_n5)

The following defined symbols remain to be analysed:
sieve'

They will be analysed ascendingly in the following order:
sieve' = activate'

Could not prove a rewrite lemma for the defined symbol sieve'.

Lemmas:
activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, _n5))) → _*4, rt ∈ Ω(_n5)

No more defined symbols left to analyse.

The lowerbound Ω(n) was proven with the following lemma:
activate'(_gen_0':n__s':n__from':n__filter':n__sieve':n__cons'3(+(1, _n5))) → _*4, rt ∈ Ω(_n5)