# 99 questions/Solutions/34

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

m |
|||

Line 10: | Line 10: | ||

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 | 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: | ||

+ | <haskell> | ||

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

+ | </haskell> |

## Revision as of 20:50, 19 January 2011

(**) 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]