[Haskell-cafe] Is there an efficient way to generate Euler's totient function for [2, 3..n]?
kc1956 at gmail.com
Sat May 14 19:38:03 CEST 2011
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]
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
More information about the Haskell-Cafe