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

[Henning Thielemann]

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.