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 <warren.henning@gmail.com> wrote:
On Sat, May 14, 2011 at 10:22 AM, KC <kc1956@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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- -- Regards, KC