# 99 questions/Solutions/34

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

(**) Calculate Euler's totient function phi(m).

Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.

```totient 1 = 1
totient a = length \$ filter (coprime a) [1..a-1]
where coprime a b = gcd a b == 1
```

We take coprime from the previous exercise and give it to filter, which applies it to each element of a list from 1 to one less than the number, returning only those that are true. length tells us how many elements are in the resulting list, and thus how many elements are coprime to n

Or slightly more concise, using list comprehension:

```totient n = length [x | x <- [1..n], coprime x n]
```

For very large numbers, however, the above algorithms become very slow. The Wikipedia article for Euler's totient function provides an algorithm that uses the number's prime factors.

```import Data.List (nub)
import Data.Ratio
totient :: (Integral a) => a -> a
totient 1 = 1
totient n = numerator ratio `div` denominator ratio
where ratio = foldl (\acc x -> acc * (1 - (1 % x)))
(n % 1) \$ nub (primeFactors n)
```

This example uses Data.Ratio to ensure no precision is lost. It also relies on a function primeFactors (not shown) that returns a list of all a number's prime factors.