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

Instead of finding the totient of one number, is there a quicker way when processing a sequence? -- From: http://www.haskell.org/haskellwiki/99_questions/Solutions/34 totient :: Int -> Int totient n = length [x | x <- [1..n], coprime x n] where coprime a b = gcd a b == 1 On Sat, May 14, 2011 at 10:29 AM, Warren Henning wrote:

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.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- -- Regards, KC