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

22 May 2011


      Daniel Fischer schrieb:
...
On Saturday 14 May 2011 19:38:03, KC wrote:
...
Instead of finding the totient of one number, is there a quicker way
when processing a sequence?
For some sequences.
You may find alternative ways of computation in the Online Encyclopedia
of Integer Sequences.

http://oeis.org/A000010
...
...
-- 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
NEVER do that! It's awfully slow.
It's declarative and may help to verify more efficient implementations.

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

Henning Thielemann