[Haskell-cafe] Is there an efficient way to generate Euler's totient function for [2, 3..n]?

[Warren Henning]

On Sat, May 14, 2011 at 10:22 AM, KC <kc1956 at gmail.com> wrote:
> Is there an efficient way to generate Euler's totient function for [2,3..n]?
>
> Or an arithmetical sequence?
>
> Or a geometric sequence?
>
> Or some generalized sequence?

Does computing the totient function require obtaining the prime
factorization of an integer, which can't be done in polynomial time?

Maybe I misunderstood what you were saying.