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