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

[KC]

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
<warren.henning at gmail.com> wrote:
> On Sat, May 14, 2011 at 10:22 AM, KC <kc1956 at gmail.com> 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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
--
Regards,
KC