[Haskell-cafe] Is there an efficient way to generate Euler's totient function for [2, 3..n]?
schlepptop at henning-thielemann.de
Sun May 22 18:27:36 CEST 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.
>> -- From: http://www.haskell.org/haskellwiki/99_questions/Solutions/34
>> totient :: Int -> Int
>> totient n = length [x | x <- [1..n], coprime x n]
>> 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.
More information about the Haskell-Cafe