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 <[email protected]> wrote: > On Sat, May 14, 2011 at 10:22 AM, KC <[email protected]> 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- -- Regards, KC _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
