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

On Sat, May 14, 2011 at 10:22 AM, KC 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.