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

[KC]

> It's declarative and may help to verify more efficient implementations.

WOW! Good insight. :)


On Sun, May 22, 2011 at 9:27 AM, Henning Thielemann
<schlepptop at henning-thielemann.de> wrote:
> 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.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
--
Regards,
KC