Difference between revisions of "99 questions/Solutions/34"
< 99 questions | Solutions
Jump to navigation
Jump to search
(No difference)
|
Revision as of 16:53, 13 July 2010
(**) 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