Difference between revisions of "99 questions/Solutions/34"
< 99 questions | Solutions
Jump to navigation
Jump to search
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]